Straightforward DFS Java solution with explanation


  • 0
    L
    public class Solution {
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        helper(root);
    }
    //definetion: flatten the tree with this root and return the tail of its flattend list
    //invariant: tail musn't be null, root musn't be null
    public TreeNode helper(TreeNode root){
        //at this moment, I can guarantee that root is not null
        
        //4 cases:
        //1.have both children
        //2.have left child and right child is null
        //3.have right child and left child is null
        //4.have no children
        if (root.left != null && root.right != null){
            TreeNode tmpRight = root.right;
            root.right = root.left;
            root.left = null;
            TreeNode tailOfLeft = helper(root.right);
            tailOfLeft.right = tmpRight;
            return helper(tmpRight);
        }
        else if (root.left != null && root.right == null){
            root.right = root.left;
            root.left = null;
            return helper(root.right);
        }
        else if (root.left == null && root.right != null){
            return helper(root.right);
        }
        else {
            return root;
        }
    }
    

    }


Log in to reply
 

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