1101 words

6 minutes

Page Views

二叉树知识\刷题总结

2025-07-09

Leetcode

Binary Tree

知识来源：labuladong的算法笔记

二叉树基础#

满二叉树(Perfect Binary Tree)#

所有父节点都有两个子节点节点数：等比数列求和 n = 2^h - 1，h代表树的深度

完全二叉树(Complete Binary Tree)#

每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的。

其性质决定它可以用数组来存储，不需要真的构建链式节点。

且完全二叉树的左右子树中，至少有一棵是满二叉树

二叉搜索树(Binary Search Tree) BST#

对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。你可以简单记为「左小右大」

高度平衡二叉树(Height-Balanced Binary Tree)#

每个节点左右子树高度差不得超过1

假设高度平衡二叉树中共有 N 个节点，那么高度平衡二叉树的高度是 O(logN)

如果能保证树的高度为 O(logN)，那么这些数据结构的增删查改效率就会很高。

自平衡二叉树(Self-Balanced Binary Tree)#

通过左旋右旋，让树的高度始终是平衡的例子：红黑树

二叉树的实现方法#

常规方法：

1
class TreeNode {
2
public:
3
    int val;
4
    TreeNode* left;
5
    TreeNode* right;
6
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
7
};
8

9
// 你可以这样构建一棵二叉树：
10
TreeNode* root = new TreeNode(1);
11
root->left = new TreeNode(2);
12
root->right = new TreeNode(3);
13
root->left->left = new TreeNode(4);
14
root->right->left = new TreeNode(5);
15
root->right->right = new TreeNode(6);
16

17
// 构建出来的二叉树是这样的：
18
//     1
19
//    / \
20
//   2   3
21
//  /   / \
22
// 4   5   6

其他方法：

用哈希表表示二叉树，键存父节点id，值存子节点id (又称邻接表)

1
// 1 -> {2, 3}
2
// 2 -> {4}
3
// 3 -> {5, 6}
4

5
unordered_map<int, vector<int>> tree;
6
tree[1] = {2, 3};
7
tree[2] = {4};
8
tree[3] = {5, 6};

还有二叉堆、并查集

二叉树的递归/层序遍历#

递归->DFS, 层序->BFS

递归遍历#

先序、中序、后序（记忆父节点的访问时机）：中左右、左中右、左右中

而对于框架的修改，先、中、后的区别只有操作代码在traverse中的的位置

二叉树递归遍历的框架#

1
// 基本的二叉树节点
2
class TreeNode {
3
public:
4
    int val;
5
    TreeNode* left;
6
    TreeNode* right;
7

8
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
};
10

11
// 二叉树的递归遍历框架
12
void traverse(TreeNode* root) {
13
    if (root == nullptr) {
14
        return;
15
    }
16
    //先序位置
17
    traverse(root->left);
18
    //中序位置
19
    traverse(root->right);
20
    //后序位置
21
}

其中，BST的中序遍历是有序的

层序遍历（BFS）#

用的比较多的写法：

1
void levelOrderTraverse(TreeNode* root) {
2
    if (root == nullptr) {
3
        return;
4
    }
5
    queue<TreeNode*> q;
6
    q.push(root);
7
    // 记录当前遍历到的层数（根节点视为第 1 层）
8
    int depth = 1;
9

10
    while (!q.empty()) {
11
        // 队列的长度
12
        int sz = q.size();
13
        for (int i = 0; i < sz; i++) {
14
            TreeNode* cur = q.front();
15
            q.pop();
16
            // 访问 cur 节点，同时知道它所在的层数
17
            cout << "depth = " << depth << ", val = " << cur->val << endl;
18

19
            // 把 cur 的左右子节点加入队列
20
            if (cur->left != nullptr) {
21
                q.push(cur->left);
22
            }
23
            if (cur->right != nullptr) {
24
                q.push(cur->right);
25
            }
26
        }
27
        depth++;
28
    }
29
}

例题 leetcode 111. 二叉树的最小深度 #

核心思想：层序遍历BFS，使用队列，当第一次遇到叶子结点时，此时的深度就是最小深度。

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10
 * };
11
 */
12
class Solution {
13
public:
14
    int minDepth(TreeNode* root) {
15
        if(root == nullptr){
16
            return 0;
17
        }
18
        int depth = 1;
19
        queue<TreeNode*> q;
20
        q.push(root);
21
        while(!q.empty()){
22
            int sz = q.size();
23
            // cout<<sz<<endl;
24
            for(int i=0; i<sz; i++){
25
                TreeNode* cur = q.front();
26
                q.pop();
27
                if(cur->left == nullptr && cur->right == nullptr){
28
                    return depth;
29
                }
30
                if(cur->left != nullptr){
31
                    q.push(cur->left);
32
                }
33
                if(cur->right != nullptr){
34
                    q.push(cur->right);
35
                }
36
            }
37
            depth++;
38
        }
39
        return 0;
40
    }
41
};

例题 104. 二叉树的最大深度#

核心思想：盲猜应该是DFS，对的

递归，进入结点时增加深度。退出结点时减少深度。在这个过程中用两个外部变量记录，取max

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10
 * };
11
 */
12
class Solution {
13
public:
14
    int res = 0;
15
    int depth = 0;
16

17
    int maxDepth(TreeNode* root) {
18
        traverse(root);
19
        return res;
20
    }
21
    void traverse(TreeNode* root){
22
        if(root == nullptr) return;
23

24
        depth++;
25
        if(root->left == nullptr && root->right == nullptr) res = std::max(depth,res);
26
        traverse(root->left);
27
        traverse(root->right);
28
        depth--;
29
    }
30
};