Flatten Binary Tree to Linked List @LeetCode

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

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

	package leetcode.tree;
	import java.util.LinkedList;
	import leetcode.tree.InorderTraversal.TreeNode;
	public class FlatternBinaryTreeToLinkedList {
	/**
	* Solution1: Tree Reconstruct -- Handle left Tree, then hanlde right tree.
	* Except first time, lastNode will not be null, everytime,
	* lastNode.left == null ---> cut down left tree
	* lastNode.right == root ---> move left tree to right node.(will not miss right,
	* because right tree already stored in previous recursion)
	* lastNode = root --> move depth
	*
	* Take Care: remember to store right tree, or when flatten(right), right tree will not original one
	*
	*/
	public TreeNode lastNode = null;
	public void flatten(TreeNode root) {
	if (root == null) {
	return;
	}
	if (lastNode != null) {
	lastNode.left = null;
	lastNode.right = root;
	}
	lastNode = root;
	TreeNode right = root.right;
	flatten(root.left);
	flatten(right);
	}
	/**
	* Solution2: Travesal
	* My though: It's a preorderTraversal, So I can traversal all tree nodes, and sotres in a LinkedList,
	* So this LinkedList can meets need. But we still need to convert this Tree.
	*
	* Defect: need to reconstruct -- poor efficiency
	* @param root
	*/
	public void flatten2(TreeNode root) {
	LinkedList<TreeNode> list = new LinkedList<TreeNode>();
	TreeNode node = root;
	traversal(list, node);
	// ReConstruct this Tree
	for (int i=1; i< list.size(); i++) {
	root.left = null;
	root.right = list.get(i);
	root = root.right;
	}
	}
	private void traversal(LinkedList list, TreeNode node) {
	if (node == null) {
	return;
	}
	list.add(node);
	traversal(list, node.left);
	traversal(list, node.right);
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw FlatternBinaryTreeToLinkedList.java hosted with ❤ by GitHub