LeetCode 156: Binary Tree Upside Down

https://leetcode.com/problems/binary-tree-upside-down/


Notes:
For tree-related questions, we usually can think about recursion. To this question, one way to think about it is that if we can finish f(root->left), then we just need to set root->left->right to the root, root->left->left to the root->right. and set root->left = NULL, and root->right = NULL. Done.

This is a bottom-up recursion.

See the code below:

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if (!root || !root->left) return root;//base case
        TreeNode *l = root->left, *r = root->right;
        TreeNode *res = upsideDownBinaryTree(l);
        l->left = r;
        l->right = root;
        root->left = NULL;
        root->right = NULL;
        return res;
    }
};

A second way to solve this problem: iterative scan in a top-down fashion. Actually it is very similar to reverse a LinkedList.

See the code below:

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        TreeNode *cur = root, *pre = NULL, *next = NULL, *tmp = NULL;
        while (cur) {
            next = cur->left;
            cur->left = tmp;
            tmp = cur->right;
            cur->right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};