Share my java recursive & iterative solution with comments


  • 0
    M
    public class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if (root==null || root.left==null) { return root; }  // the new root of the upside-down tree
            TreeNode newRoot = upsideDownBinaryTree(root.left);
            TreeNode newParent = root.left;  // the new parent of current level is originally the left child
            newParent.left = root.right;
            newParent.right = root;
            newParent.right.left = null;  // set original parent's left and right pointer to null, otherwise there will be a loop at the last backtracking level
            newParent.right.right = null;
            return newRoot;
        }
    }
    

    As we can see, this is just tail-recursion, so we can easily translate it into iterative version.

    public class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if (root == null) { return null; }
            List<TreeNode> s = new ArrayList<>();  // our own stack
            for (TreeNode p=root; p!=null; p=p.left) { s.add(p); }
            for (int i=s.size()-2; i>=0; --i) {
                TreeNode oldParent = s.get(i);
                TreeNode newParent = oldParent.left;
                newParent.left = oldParent.right;
                newParent.right = oldParent;
                oldParent.left = null; oldParent.right = null;
            }
            return s.get(s.size()-1);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.