Flatten Binary Tree to Linked List (Java)

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution:

Divide and Conquer, convert left and right tree to list separately, then connect root. right to list converted by left tree, make root. left to null, then search for the lastNode of right tree and connect it to list converted by original right tree.

	Flatten Binary Tree to Linked List
	Given a binary tree, flatten it to a linked list in-place.
	For example,
	Given
	1
	/ \
	2 5
	/ \ \
	3 4 6
	The flattened tree should look like:
	1
	\
	2
	\
	3
	\
	4
	\
	5
	\
	6
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// rewrite at 2/8
	public class FlattenBinaryTreeToLinked {
	public void flatten(TreeNode root) {
	if (root==null){
	return;
	}
	covertToList(root);
	}
	private TreeNode covertToList(TreeNode root){
	if (root==null){
	return root;
	}
	// convert right tree to list
	TreeNode tempRight=covertToList(root.right);
	// convert left tree to list and connect it to right of root
	root.right=covertToList(root.left);
	// make left side to null;
	root.left=null;
	TreeNode tempRoot=root;
	// find the right most node which used to connect list coverted by original right tree
	while (tempRoot.right!=null){
	tempRoot=tempRoot.right;
	}
	tempRoot.right=tempRight;
	return root;
	}
	}
	// old version
	public class Solution {
	public void flatten(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (root==null||(root.left==null&&root.right==null)){
	return ;
	}
	else{
	if (root.left!=null){
	TreeNode temp=root.right;
	root.right=root.left;
	TreeNode rightMost=findRightMost(root.right);
	rightMost.right=temp;
	root.left=null;
	flatten(root.right);
	}
	else{
	flatten(root.right);
	}
	}
	}
	public TreeNode findRightMost(TreeNode root){
	if (root.right!=null){
	return findRightMost(root.right);
	}
	else{
	return root;
	}
	}
	}

view raw FlattenBinaryTreeToLinked List.java hosted with ❤ by GitHub