二叉树算法总结

889,331,894题跳过

递归算法

二叉树的递归问题，分为遍历和分解两种思想。

遍历

DFS 深度优先搜索，自顶向下，需要回溯，函数类型为 void，依靠全局变量（显式）或参数传递（隐式）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 定义全局变量

void traverse(TreeNode* root){
    if(root == nullptr)
        return;

    // 前序进入处理

    if(root->left == nullptr && root->right == nullptr){
        // 叶节点临界处理
    }

    traverse(root->left);
    traverse(root->right);

    // 后序回溯
}

分解

动态规划，自底向上，进行分治，函数类型为 TreeNode* （结果类型），

非递归算法

层序遍历，BFS 广度优先搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root)
        return {};
    vector<vector<int>> level;
    std::queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int sz = q.size();
        level.push_back(vector<int>(sz));
        for (int i = 0; i < sz; i++) {
            TreeNode* temp = q.front();
            level[depth][i] = temp->val;
            q.pop();
            if (temp->left)
                q.push(temp->left);
            if (temp->right)
                q.push(temp->right);
        }
        depth++;
    }
    return level;
}