PostOrder traversal recursive


  • 0
    J

    I'm surprised that no one mentioned this is actually a postorder traversal.
    left child is new root, root is new right child, and right is the new left child.

    public class Solution {
        TreeNode ans = null;
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            reverse(root);
           return ans; 
        }
        
        public TreeNode reverse(TreeNode root){
            if(root==null || root.left==null){
                if(ans==null) ans = root;
                return root;
            }
            TreeNode newRoot = reverse(root.left);
            TreeNode newLeft = reverse(root.right);
            newRoot.left = newLeft;
            newRoot.right = root;
            // if(root==null) System.out.println("root");
            // if(newRoot==null) System.out.println("newRoot");
            // if(newLeft==null) System.out.println("newLeft");
            // System.out.println(newRoot==null?0:newRoot.val + " " + newLeft==null?0:newLeft.val+ " " + root==null?0:root.val);
            root.left = null;
            root.right = null;
            return root;
        }
    }
    

Log in to reply
 

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