LeetCode OJ 114. Flatten Binary Tree to Linked List

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

For example,
Given

The flattened tree should look like:

   1
    
     2
      
       3
        
         4
          
           5
            
             6

这个问题的解决我首先想到的是用递归的方法。
1.把根节点的左子树转换为链表的形式；
2.把根节点的右子树转换为链表的形式；
3.把左子树合并到右子树中；

在把左子树链表合并到右子树链表的过程中，如果左子树为null，则直接返回。否则找到左子树链表的尾节点，并把整个链表插入到根节点和根节点右子树链表的第一个节点之间。代码如下：

 1 public class Solution {
 2     public void flatten(TreeNode root) {
 3         if(root == null) return;
 4         if(root.left==null && root.right==null) return;
 5         
 6         TreeNode leftpointer = root.left;
 7         if(root.left!=null){
 8             flatten(root.left);
 9             while(leftpointer.right!=null){
10                 leftpointer = leftpointer.right;
11                 
12             }
13         }
14         if(root.right!=null) flatten(root.right);
15         
16         if(root.left!=null){
17             leftpointer.right = root.right;
18             root.right = root.left;
19             root.left = null;
20         }
21         
22         return;
23     }
24 }