my clean divide & conquer java solution


  • 0
    L

    General idea: put left subtree in the right subtree, put right subtree under the tail of left subtree.
    '''

    public class Solution {
       public void flatten(TreeNode root) {
        TreeNode tail = flattenBT(root);
    }  
       private TreeNode flattenBT(TreeNode root) {
          if(root == null) {
             return null;
         }
        
        TreeNode leftTail = flattenBT(root.left);
        TreeNode rightTail = flattenBT(root.right);
        //only if left subtree exists
        if(root.left != null) {
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = null;
            leftTail.right = temp;
        }
        //when we need to return, consider three different situations: right subtree exists,left subtree exists, or both don't exist; 
        if(rightTail != null) {
            return rightTail;
        }
        
        if(leftTail != null) {
            return leftTail;
        }
        
        return root;
    }
    

    }
    '''


Log in to reply
 

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