Leetcode 156. Binary Tree Upside Down

Description:

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:Given a binary tree {1, 2, 3, 4, 5}

return the root of the binary tree[4,5,2,#,#,3,1].

Thinking:

For the given example, we find that the final upside down tree's root is the leftmost leafnode. And we also find the process of upside down follows the rule that:
current.left.left = current.right
current.left.right = current

Steps:

Check the input, ifroot == null, then we just returnnull.
Recursion or iteration? The below attached both recursive and iterative codes. But when I first met this problem, I decided to use recursion. Becuase it will defintely use prev and next pointer to store the TreeNode information in iteration. However, by using the recursion, we only need to think about the condition that we need toreturn And to deal with the current TreeNode.
Do we need to create a helper function? Since in the process of recursion. We don't need to use other information except the root itself. So it's not necessary for us to create a helper function.
How to do the recursion? we need to callFun(root.left) again and again until it reaches the leftmost leafnode.
Determinereturn condition. Typically, we need to think about root == null for one of the return condition. And in this problem, we also need to think aboutroot.left == null && root.right == null. Because it means that we have already reach the leftmost leafnode. And we need to use more than one level of the tree during the recursion. That's also the reason we need the condition root.left and root.right.
There is one thing we should note that, after we complete the process of upside down. We need to setcurrent.left == null and current.right == null. Because its bottom-up process for recursion. we don't have this problem in iterative way.

Code:

Recursive:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) return null;
        if(root.left == null && root.right == null){
            return root;
        }
        TreeNode newroot = upsideDownBinaryTree(root.left);
        root.left.left = root.right;
        root.left.right = root;

        root.left =null;    //We should be careful!!!!!!!!!!!!!!
        root.right = null;

        return newroot;
    }
}

Iterative:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) return null;
        TreeNode current = root;
        TreeNode prev = null;
        TreeNode next = null;
        TreeNode temp = null;
        while(current != null){
            next = current.left;
            current.left = temp;
            temp = current.right;
            current.right = prev;

            prev = current;
            current = next;
        }
        return prev;
    }
}

Conclusion:

We need to have prev/next to store information in the iterative method if we want to change the structure (of the tree). And we need to use more than one level's information of the tree(not only use the current Node), which is like the problem of Leetcode 345. Reverse Linked List

Leetcode 156. Binary Tree Upside Down