理论基础

二叉树的种类：

  • 满二叉树：二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上
  • 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。（例如大顶堆和小顶堆就是这种数据结构）
  • 二叉搜索树：二叉搜索树是一个有序树，左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。
  • 平衡二叉树：左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn。

遍历框架

递归遍历（DFS）

1
2
3
4
5
6
7
8
9
10
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

1、144二叉树的前序遍历、145二叉树的后序遍历、94二叉树的中序遍历

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
// 前
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};
//中
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}
//后
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

2、二叉树的迭代遍历

先放过

3、二叉树的统一迭代法

先放过

4、二叉树的层序遍历

labuladong框架：

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
// 1、层序遍历
void levelTraverse(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* cur = q.front();
        // *****条件***** //
        q.pop();
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

// 2、for循环记录层数
void levelTraverse(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            // *****条件***** //
            q.pop();
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
    }
}

4.1 102二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
直接套框架:

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr)return vector<vector<int>>();

        queue<TreeNode*>  pq;
        pq.emplace(root);
        vector<vector<int>> res;

        while(!pq.empty()){
            auto num = pq.size();
            vector<int> res_t(num);
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                res_t[i] = cur->val;
                pq.pop();

                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
            }
            res.emplace_back(res_t);
        }
        return res;
    }

    
};

4.2 107二叉树的层序遍历II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

我的思路： 比较容易想到的方法就是正常层序遍历然后最后reverse一下就可以。

1
2
... 
reverse(res.begin(),res.end());

4.3 199二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

我的思路： 和就是层序遍历，只不过每一层只要一个元素。

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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr)return vector<int>(); 
        queue<TreeNode*>  pq;
        pq.emplace(root);

        vector<int> res;

        while(!pq.empty()){
            auto num = pq.size();
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                pq.pop();

                if(i==0){
                    res.emplace_back(cur->val);
                }

                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
            }
        }
        return res;
    }
};

4.4 637二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

我的思路： 还是带for循环版本的层序遍历。最后发现有一个案例，全是int最小值过不了。64 / 66 个通过的测试用例。 我用int sum去求和提示溢出，于是我把每个元素除以size先求平均值再相加。这样应该会损失精度。后面改为long long sum就可以了。测试double sum也可以。double 类型可以表示大约 15-17 位有效数字，用来表示整数(10位左右)足够了。

1
2
3
4
5
6
# 案例
-2147483336-2147483647-2147483646-2147483647-2147483647-2147483647-2147483644-2147483647-2147483647-2147483525-2147483647-2147483647-2147483646-2147483646-2147483646 ...
# 我的输出
[0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,-0.00002]
# 正确输出
[0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
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
// 我的代码
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if(root == nullptr)return vector<double>(); 
        queue<TreeNode*>  pq;
        pq.emplace(root);

        vector<double> res;

        int k = 0;

        while(!pq.empty()){
            auto num = pq.size();
            double ave = 0.0;
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                if(cur->val!=0){
                    ave+=static_cast<double>(cur->val)/num;
                }
                
                pq.pop();

                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
            }
            res.emplace_back(ave);
            k++;
        }
        return res;
    }
};

// 看了代码随想录后的
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if(root == nullptr)return vector<double>(); 
        queue<TreeNode*>  pq;
        pq.emplace(root);

        vector<double> res;

        while(!pq.empty()){
            auto num = pq.size();
            double sum = 0;
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                sum+=cur->val;
                
                pq.pop();

                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
            }
            res.emplace_back(sum/num);
        }
        return res;
    }
};

4.5 429N叉树的层序遍历

我的思路： 简单，就是二叉树的拓展。

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
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if(root == nullptr)return vector<vector<int>>(); 
        queue<Node*>  pq;
        pq.emplace(root);

        vector<vector<int>> res;

        while(!pq.empty()){
            auto num = pq.size();
            vector<int> res_t(num);
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                res_t[i] = cur->val;
                pq.pop();

                for(auto node_t:cur->children){
                    if(node_t!=nullptr){
                        pq.push(node_t);
                    }
                }
            }
            res.emplace_back(res_t);
        }
        return res;
    }
};

4.6 515在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

我的思路： 层序遍历框架。

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
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if(root == nullptr)return vector<int>(); 
        queue<TreeNode*>  pq;
        pq.emplace(root);

        vector<int> res;

        while(!pq.empty()){
            auto num = pq.size();
            int max = INT_MIN;
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                if(cur->val > max){
                    max = cur->val;
                }
                
                pq.pop();

                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
            }
            res.emplace_back(max);
        }
        return res;
    }
};

4.7 116填充每个节点的下一个右侧节点指针

给定一个 完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}


我的思路： 层序遍历。只是应该存储上一次的节点。

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
// 我写的，代码不是很漂亮，思路是对的
class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr)return root; 
        queue<Node*>  pq;
        pq.emplace(root);

        while(!pq.empty()){
            auto last = pq.front();
            pq.pop();
            auto num = pq.size();
            if(last->left!=nullptr){
                pq.emplace(last->left);
            }
            if(last->right!=nullptr){
                pq.emplace(last->right);
            }
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                last->next = cur;
                last = cur;
                pq.pop();

                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
            }
            last->next = nullptr;
        }
        return root;
    }
};
//代码随想录
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            // vector<int> vec;
            Node* nodePre;
            Node* node;
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = que.front(); // 取出一层的头结点
                    que.pop();
                    node = nodePre;
                } else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;
    }
};

4.8 117填充每个节点的下一个右侧节点指针II

Same to 4.7 116填充每个节点的下一个右侧节点指针

4.9 104二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

我的思路： 层序遍历。每层计数。

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
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr)return 0; 
        queue<TreeNode*>  pq;
        pq.emplace(root);

        int depth = 0;

        while(!pq.empty()){
            auto num = pq.size();
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                pq.pop();

                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
            }
            depth++;
        }
        return depth;
    }
};

4.10

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。

我的思路： 层序遍历。和最大深度区别是找到一个叶子节点就停。

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
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr)return 0; 
        queue<TreeNode*>  pq;
        pq.emplace(root);

        int depth = 0;

        while(!pq.empty()){
            auto num = pq.size();
            for(int i = 0;i<num;i++){
                auto cur = pq.front();
                pq.pop();

                if(cur->left==nullptr && cur->right==nullptr){
                    return depth+1;
                }
                if(cur->left!=nullptr){
                    pq.emplace(cur->left);
                }
                if(cur->right!=nullptr){
                    pq.emplace(cur->right);
                }
            }
            depth++;
        }
        return depth;
    }
};