flatten binary tree

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 114. Flatten Binary Tree to Linked List

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

程序中DFS过程先一直向右走（ flatten (root->right);），直到遇到空节点再一直向左走（flatten (root->left);），直到遇到空节点再处理节点本身，这是典型的R - L - V 顺序的后续遍历。 处理完node 的 右子树、左子树后 再处理node， 最后让prev指向node。
例如

  • root指针一直向右走，直到走到节点6，它的rc为空，flatten(6->right) return， 于是运行下一句 flatten(6->left), 6的lc也为空， 于是return，这样6的右、左都处理完了， 开始设置6本身。 设置好后让prev指向6…后面以此类推。
0%