Flatten a Binary Tree in Java

package sachi.test.datastructures;

import java.util.LinkedList;

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;

}

}

}