Clean straight forward postorder solution! Easy to understand!


  • 2

    I came up with another postorder solution, the idea is simple:
    (1) flatten left subtree, return its tail node 'leftTail'
    (2) flatten right subtree, return its tail node 'rightTail'
    (3) if left subtree exists and has been flattened, we need to move it to the right:
    set flattened right subtree as leftTail.right
    set flattened left subtree to be the new right subtree(root.right)
    set root.left=null
    (4) return the tail node of this flattened tree (return rightTail if it isn't null, else return leftTail if it isn't null, else return root)
    0_1507853437658_Screen Shot 2017-10-12 at 5.10.04 PM.png
    I change the return type in order to keep only one recursive fuction, it works for leetcode:)

    public TreeNode flatten(TreeNode root) {
        if(root==null) return null;
        TreeNode leftTail = flatten(root.left);
        TreeNode rightTail = flatten(root.right);        
        if(root.left!=null) {
            leftTail.right = root.right;
            root.right=root.left;
            root.left=null;
        }        
        return rightTail!=null?rightTail:(leftTail!=null?leftTail:root);
    }

  • 0

    @tongzhou2 I guess this is postorder traversal, not preorder.


  • 0

    @jeantimex Hey thanks for your reply, hmm I agree with u!
    BTW haven't seen your in leetcode for a while, how is it going?


  • 0

    @tongzhou2 Been busy on my open source projects, in the meantime, trying to solve leetcode problems using JavaScript. I like your solution!


  • 0

    @jeantimex Oh man that's awesome!


Log in to reply
 

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