Inplace 1 ms Java solution using recursion. Well commented and easy to understand

  • 1
    public void flatten(TreeNode root) {
    	  /** this methid returns the last preorder node of the root*/
    	  public TreeNode flattenRoot(TreeNode root){
    		  TreeNode last = root;
    		  TreeNode left = root.left, right = root.right; // grab the left and right 
    		  root.left = root.right = null; // reset left and right to avoid any pointer pitfalls in recursion
    		  if(left != null){ // check if we need to traverse left node child
    			  last = flattenRoot(left); // flat the left child first which will return the last child in its path
    			  root.right = left; // set root's right to its according to preorder
    		  // till now we have left node flatten list and last pointer of left node 
    		  if(right != null){ // if right node exists 
    			  last.right = right; // assign last node right to current node's right as per preorder
    			  last = flattenRoot(right); // now assign last to last node of right preorder.
    	      return last;

  • 0

    This is great. I thought of this very same approach but couldn't code it up this easily :) . Thanks for sharing

  • 0

    Thanks for the appreciation :D.

Log in to reply

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