114. 二叉树展开为链表

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

Solution1：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root) return;
        dfs(root);
    }
    
    TreeNode* dfs(TreeNode* node){
        if(!node->left && !node->right) return node;
        TreeNode* lastLeft = NULL;
        TreeNode* lastRight = NULL;
        if(node->left){
            lastLeft = dfs(node->left);
        }
        if(node->right){
            lastRight = dfs(node->right);
        }
        if(lastLeft){
            lastLeft->right = node->right;
            node->right = node->left;
            node->left = NULL;
        }
        
        if(lastRight) return lastRight;
        else return lastLeft;
    }
};

思路：

从叶子结点开始，向上展开。每到一层，分别获得左子树和右子树的最后节点，将左子树的最后节点与当前节点的右子树的开始节点连接，将当前节点的右节点指向左子树的开始节点，左子树置空。

接着返回当前子树的最后节点，作为上一层的相应结点做相应的处理。

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void flatten(TreeNode* root) {
        dfs(root);
    }
    
    TreeNode* dfs(TreeNode* node){
        if(!node) return NULL;
        TreeNode* lastLeft;
        TreeNode* lastRight;
        lastLeft = dfs(node->left);
        lastRight = dfs(node->right);
        if(lastLeft){
            lastLeft->right = node->right;
            node->right = node->left;
            node->left = NULL;
        }
        return lastRight ? lastRight : lastLeft ? lastLeft : node ;
    }
};

将空节点做一般化考虑，在返回的时候做相应的处理。

分几种情况：

  • 有lastRight，优先返回lastRight，

  • 没有lastRight，有lastLeft，此时由于之上的代码已经将子树展开为链表并转换到了右子树上面，这时返回lastLeft。

  • lastRight 和 lastLeft 都没有，这时为叶子节点，直接返回该节点即可。

Solution2（终极版）：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* prev = NULL;
    void flatten(TreeNode* root) {
        if(!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = NULL;
        prev = root;
    }
};

看到评论区大神写的这段代码，我觉得我被虐的体无完肤。

首先，设置一个全局变量，该变量用来记录已经翻转过的开始结点。
接着，递归是首先下到最右边，从最右边开始的，这就保证了只需要关心已经展开链表的头结点，尾结点没必要再关心了。每次到达一个子树，从最右的结点开始，每个节点接到全局变量上。全局变量刷新为新的展开链表的头。如此一直到达根节点。