[Java] Bottom-up recursive solution with comments


  • 0
    K

    Typical bottom-up tree construction.

    Suppose at current level, we have parent and current (which is parent.left), According to the definition of the up-side-down.

    The operation are:

    1. current.left = parent.right
    2. current.right = parent;

    Do it and you will get solution.

        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if(root == null || root.left == null) return root;
            return dfs(root, root.left);
        }
        
        private TreeNode dfs(TreeNode parent, TreeNode curr) {
            // Reach the left most leaf
            if(parent.left == null && parent.right == null) return parent;
            
            TreeNode root = dfs(parent.left, parent.left.left);
            
            // Curr right now is the left most leaf,
            if(curr.left == null && curr.right == null) {
                curr.left = parent.right;
                curr.right = parent;
                parent.left = null;
                parent.right = null;
            }
            
           return root;
            
        }
    

Log in to reply
 

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