453 - 두 갈래 나무를 체인 시계로 분해

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
   public void flatten(TreeNode root) {
       if(root == null){
        	return;	
        }
        LinkedList list = new LinkedList();
        LinkedList queue = new LinkedList();
        TreeNode bt = root;
        while(bt != null || !list.isEmpty()){// write your code here
        	while(bt != null){
        		//System.out.print(bt.val + " ");
        		queue.addLast(bt);
        		list.push(bt);
        		bt = bt.left;
        		
        	}
        	if(!list.isEmpty()){
        		bt = list.pop();
        		//System.out.print(tmp.val + " ");
        		bt = bt.right;
        	}	
        }
        
        //System.out.print("
");
        root = queue.pop();
        bt = root;
        //System.out.print("
" + bt.val + " ");
        while(!queue.isEmpty()){
        	bt.left = null;
        	bt.right = queue.getFirst();
        	bt = queue.pop();
        	//System.out.print(bt.val + " ");
        }
        bt.left =bt.right = null;
   }
}