题目

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树：

1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

题解 + 思路

一开始想的是递归，但是递归是由底向顶递归生成，而这道题是由顶到底生成，虽然存在子问题，但是仍难以求解。

其实可以看做如下步骤：

  1. 找到左子树的最右节点。
1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6
  1. 将右子树移到左子树的最右节点。
1
2
3
4
5
6
7
8
9
    1
   / 
  2   
 / \   
3   4
     \
      5
       \
        6
  1. 右子树换为左子树，左子树置为 null
1
2
3
4
5
6
7
8
9
1
 \
  2   
 / \   
3   4
     \
      5
       \
        6
  1. 从右节点开始，继续该操作
1
2
3
4
5
6
7
8
9
10
11
1
 \
  2   
   \   
    4
     \
      5
       \
        6
         \
          3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
       while(root!=null){
           if(root.left==null){
               root=root.right;
           }else{
               TreeNode pre  = root.left;
               while(pre.right!=null){
                   pre = pre.right;
               }
               pre.right = root.right;
               root.right = root.left;
               root.left = null;
               root = root.right;
           }
       }
    }
}