Share my accepted recursive solution with comments - Java


  • 19
    L

    The idea is very simple:

    1. flatten left subtree

    2. flatten right subtree

    3. concatenate root -> left flatten subtree -> right flatten subtree

       public void flatten(TreeNode root) {
           if(root == null)
       	return;
       	
           flatten(root.left);
           flatten(root.right);
       
           // save current right for concatination
           TreeNode right = root.right;
       
           if(root.left != null) {
           
               // step 1: concatinate root with left flatten subtree
           	root.right = root.left;
           	root.left = null; // set left to null
       	
           	// step 2: move to the end of new added flatten subtree
           	while(root.right != null)
           		root = root.right;
       		
           	// step 3: contatinate left flatten subtree with flatten right subtree	
           	root.right = right;
           }
       }

  • 0
    Y

    I think the time complexity of your code is greater than O(n). Due to step 2: move to the end of new added flatten subtree, it takes more than O(1) to move to the end, and concatenate root -> left flatten subtree -> right flatten subtree.


  • 0
    Y

    Oh, I am wrong. I see that. The time complexity is still O(n). If we consider the while loop separately, the total time spent in while loop is n / 2 + n / 4 + ... + 1 = O(n). Besides the while loop, it takes O(n) to visit each node and do the modification of children stuff. Thus, the total time complexity is O(n).


Log in to reply
 

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