四、二叉树-上（Binary tree）

一、算法核心思想

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分！
快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

二、算法模型

（一）回溯

1.104.二叉树的最大深度

（1）思路

如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为max(l,r)+1，而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root -> left),maxDepth(root -> right)) + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（3）复杂度分析

• 时间复杂度：O(n），其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
• 空间复杂度：O(height)，height表示二叉树的高度，递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

2.144.二叉树的前序遍历

（1）思路

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }
};
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

（3）复杂度分析

• 时间复杂度：O(n）
• 空间复杂度：O(n)

3.543.二叉树的直径

（1）思路

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
int res = 0;
    int diameterOfBinaryTree(TreeNode* root) {
         maxDepth(root);
        return res;
    }
    int maxDepth(TreeNode* root) {
        if (root == nullptr)
            return 0;
        int leftMax = maxDepth(root -> left);
        int rightMax = maxDepth(root -> right);

        int myDia = leftMax + rightMax;
        res = max(res,myDia);
        return 1 + max(leftMax,rightMax);
    }
};
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

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

（二）层序遍历

1.102.二叉树的层序遍历

（1）思路

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            vector<int> temp;
            int size = q.size();
            while (size --) {
                auto t = q.front();
                temp.push_back(t -> val);
                q.pop();
                if (t -> left) q.push(t -> left);
                if (t -> right) q.push(t -> right);
            }
            res.push_back(temp);
        }
        return res;
    }
};
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

（3）复杂度分析

• 时间复杂度：O(n）
• 空间复杂度：O(n)

2.107. 二叉树的层序遍历 II

（1）思路

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            vector<int> temp;
            int size = q.size();
            while (size --) {
                auto t = q.front();
                temp.push_back(t -> val);
                q.pop();
                if (t -> left) q.push(t -> left);
                if (t -> right) q.push(t -> right);
            }
            res.push_back(temp);
        }
        reverse(res.begin(),res.end());
        return res;

    }
};
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

（3）复杂度分析

3.199. 二叉树的右视图

（1）思路

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) return res;
        queue<TreeNode*> que;
        que.push(root);
        while (que.size()) {
            int size = que.size();
            for (int i = 0 ; i < size; i++) {
                auto t = que.front();
                que.pop();
                if (i == (size - 1)) res.push_back(t -> val);
                if (t -> left) que.push(t -> left);
                if (t -> right) que.push(t -> right);
            }
        
        }
        return res;
    }
};
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

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

4.[637.二叉树的层平均值]https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/)

（1）思路

本题就是层序遍历的时候把一层求个总和在取一个均值。

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        if (root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
    
            int size = q.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                auto t = q.front();
                 q.pop();
                    sum += t->val;
                    if (t -> left) q.push(t -> left);
                    if (t -> right) q.push(t -> right);
            }
            res.push_back(sum / size);
        }
        return res;
    }
};
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

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

5.429. N 叉树的层序遍历

（1）思路

这道题依旧是模板题，只不过一个节点有多个孩子了

（2）代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
         queue<Node*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                Node* node = que.front();
                que.pop();
                vec.push_back(node->val);
                for (int i = 0; i < node -> children.size(); i++) {
                    if (node -> children[i]) que.push(node->children[i]);
                }
            }
         result.push_back(vec);
        }
        return result;
    }
};
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

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

6.515.在每个树行中找最大值

（1）思路

层序遍历，取每一层的最大值。

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) return res;
        queue<TreeNode*> que;
        que.push(root);
        while (que.size()) {
            int size = que.size();
            int maxValue = -INT_MIN;
            for (int i = 0 ; i < size; i++) {
                auto t = que.front();
                que.pop();
                if (t->val > maxValue) maxValue = t -> val;
                if (t -> left) que.push(t -> left);
                if (t -> right) que.push(t -> right);
            }
            res.push_back(maxValue);
        }
        return res;
    }
};
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

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

7.116. 填充每个节点的下一个右侧节点指针

（1）思路

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了！

（2）代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root == nullptr) return nullptr;
        que.push(root);
        while (que.size()) {
            int size = que.size();
            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(); // // 本层前一个节点next指向本节点
                    que.pop();
                    nodePre -> next = node;
                    nodePre = nodePre -> next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
             nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

8.117. 填充每个节点的下一个右侧节点指针 II

（1）思路

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道!

（2）代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*>que;
        if (root == nullptr) return nullptr;
        que.push(root);
        while (que.size()) {
            int size = que.size();
          
            Node* pre;
            Node* node;
            for (int i = 0; i < size; i ++) {
                if (i == 0) {
                    pre = que.front();
                    que.pop();
                    node = pre;
                }
                else {
                    node = que.front();
                    que.pop();
                    pre -> next = node;
                    pre = pre -> next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            pre -> next = nullptr;
        }
        return 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

9.104. 二叉树的最大深度

（1）思路

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

（2）代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root -> right),maxDepth(root -> left)) + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$

10.[111. 二叉树的最小深度(https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/)

（1）思路

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点。

（2）代码

广度优先！
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
         if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            // 我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;

    }
};
深度优先：
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        // 其次，若当前节点的左右子节点均存在，说明***当前节点不是叶子节点，其孩子节点的性质也无法判定***，故返回较小的孩子节点深度
        if(root->left && root->right) return 1 + min(minDepth(root->left), minDepth(root->right));
        //   // 最后，若当前节点的左右子节点有一个不存在，则说明***当前节点的子节点中存在叶子节点***，故返回不为空的孩子节点（叶子节点）的深度
        // 当然了，若当前节点的左右子节点都不存在，那它就是叶子节点，总深度直接 +1 就好了，也符合这个 return 句法。
        return 1 + max(minDepth(root->left), minDepth(root->right));
    }
};
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

（3）复杂度分析

• 时间复杂度：$O(n）$
• 空间复杂度：$O(n)$