Simple Java recursive method use one auxiliary node


  • 0
    Z
    TreeNode last = null; 
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        
        if(root==null) return null;
        if(root.left==null) return root;
        
        TreeNode left = upsideDownBinaryTree(root.left);
        TreeNode right = upsideDownBinaryTree(root.right);
        
        //Re-link tree nodes 
        if(last==null) last = left;
        last.left = root.right;
        last.right = root;
        
        //Remember to free the children nodes, otherwise MLE
        root.left = null;
        root.right = null;
        
        last = root;
        
        //The left most node is the new root so we return it
        return left; 
    }

  • 0
    Z

    BTW, a more simple to understand but less efficient method: When you look at the reversed tree carefully, you'll find that the upside-down tree is built from Post order traversal Therefore, you can post order traverse the tree and store them in an array, then build them from up to down.


Log in to reply
 

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