[leetcode]Flatten Binary Tree to Linked List

这个算法写的太烂，大家直接看新博文，地址：

[leetcode]Flatten Binary Tree to Linked List

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
click to show hints.

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

 状态不好就要看书，不要敲代码。囧

这道题目要求将一个二叉排序树转换成一个list，但是要就地取材in-place，不能有额外空间。典型的，是将左子树插到根节点的右子树上，然后再将右子树插到队尾，典型的前序遍历。

       TreeNode tail;//记录队尾节点
	public void flattern(TreeNode root){
		tail = root;
		doFlate(root);
	}
	private void doFlate(TreeNode root){
		if(root == null || (root.left == null && root.right == null)){
			return;
		}
		TreeNode left = root.left;
		TreeNode right = null ;
		tail = root;
		if(root.right != null){
			right = root.right;
		}
		if(left != null){
			root.right = left;
			root.left = null;
			tail = left;
		}
		doFlate(left);//处理左子树
		if(right != null){//将右子树插到队尾
			tail.right = right;
			tail = right;
		}
		doFlate(right);//再处理右子树
	}