114. 二叉树展开为链表

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

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

例如，给定二叉树

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

来源：力扣（LeetCode）
链接：114. Flatten Binary Tree to Linked List

解题思路

这题要求把二叉树展开成链表，根据展开后形成的链表的顺序分析，可以看出使用的是先（前）序遍历，即根节点->左孩子节点->右孩子节点。但凡是树的遍历，必然就有递归和非递归版本。首先来看迭代的版本。

思路和94. 二叉树的中序遍历中序遍历的Morris算法有些神似，我们需要三步完成这道题。

  • 将原来的右子树接到左子树的最右边节点
  • 将左子树插入到右子树的地方
  • 考虑右子树的节点是否有左子树，如果有则重复上述过程，直到遍历到右子树的尽头

上述过程图示如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6

代码写起来还是比较容易的，具体见解法一，里面有详细的注释。

下面来看看递归的解法，对于树的问题，如果没有用上递归，就仿佛不完整。

递归的主要思路是利用DFS的思路找到最左子节点，然后回到其父节点，把其父节点和右子节点断开，将原左子节点连上父节点的右子节点，然后再把原右子节点连到新右子节点的右子节点上，再回到上一父节点做相同的操作。

上述过程图示如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
     1
    / \
   2   5
  / \   \
 3   4   6
 
 //将最左子节点的父节点和其右子节点断开
     1
    / \
   2   5
  /     \
 3   4   6
 
 //将原左子节点连上父节点的右子节点
     1
    / \
   2   5
    \   \
     3   6  
      
       4   

 //把原右子节点连到新右子节点的右子节点
     1
    / \
   2   5
    \   \
     3   6  
      \    
       4
       
//回头上一级父节点（即为1）做相同的操作
     1
    / 
   2   5
    \   \
     3   6  
      \    
       4
       
     ||
    _||_
    \  /
     \/
     
      1
       \ 
        2   5
         \   \
          3   6  
           \    
            4   
            
     ||
    _||_
    \  /
     \/
     
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

具体代码见解法二。

代码

解法一：迭代

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


void flatten(struct TreeNode* root)
{
    //root不为空即进入循环
    while(root)
    {
        //如果左子树为NULL，则直接考虑下一个节点，将root跟新为其右孩子节点
        if(!root->left)
        {
            root = root->right;
        }
        //寻找左子树最右边的节点
        else
        {   
            //新建一个辅助节点，指向根节点的左孩子节点
            struct TreeNode* pre = root->left;
            //将这个指针移动到左子树最右边的节点
            while(pre->right)
            {
                pre = pre->right;
            }
            
            //将原来的右子树接到左子树的最右边节点
            pre->right = root->right;
            //将左子树插入到右子树的地方
            root->right = root->left;
            //将左子树置空
            root->left = NULL;
            //更新根节点
            root = root->right;
        }
    }
}

解法二：递归

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
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


void flatten(struct TreeNode* root)
{
    if(!root) return;
    
    
    
    if(root->left) 
        flatten(root->left);
    if(root->right)
        flatten(root->right);
    
    //新建节点指向最左子节点的兄弟节点
    struct TreeNode* tmp = root->right;
    //断开最左子节点的右子节点并将左子节点接上
    root->right = root->left;
    root->left = NULL;
    //遍历到新右子节点的末端
    while(root->right)
        root = root->right;
    //将原右子节点接到新右子节点的最末端
    root->right = tmp;
}

参考