【代码随想录】二叉树

发表于 更新于 分类于 阅读次数： 本文字数： 25k 阅读时长 ≈ 1:22

二叉树简介

基础概念：满二叉树、完全二叉树、二叉查找树（搜索树）、平衡二叉搜索树

二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

二叉树存储结构：顺序存储（如果双亲结点是i那么左孩子是2*i + 1，右孩子是2*i + 2)和链式存储

二叉树的遍历方式：

  • 深度优先遍历

    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）

  • 广度优先遍历

    • 层次遍历（迭代法）

    栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

    广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

    二叉树节点定义：

    1
    2
    3
    4
    5
    6
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

二叉树递归遍历

递归的方法：

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

144.二叉树的前序遍历

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
/**
 * 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 PreTraversal(TreeNode *cur, vector<int> &result) {
        // 终止条件
        if (cur == nullptr) return;

        // 首先处理当前根节点
        result.push_back(cur->val);
        // 然后处理左右孩子节点
        PreTraversal(cur->left, result);
        PreTraversal(cur->right, result);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result; // 结果数组
        PreTraversal(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
26
27
28
29
30
31
32
/**
 * 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 PreTraversal(TreeNode *cur, vector<int> &result) {
        // 终止条件
        // 空结点不会进入该函数

        // 首先处理当前根节点
        result.push_back(cur->val);
        // 然后处理左右孩子节点
        if (cur->left) PreTraversal(cur->left, result);
        if (cur->right) PreTraversal(cur->right, result);
    }


    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result; // 结果数组
        if (root) PreTraversal(root, result);
        
        return result;
    }
};

145.二叉树的后序遍历

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
/**
 * 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 PostTraversal(TreeNode *cur, vector<int> &result) {
        // 终止条件
        if (cur == nullptr) return;

        // 先处理左右孩子
        PostTraversal(cur->left, result);
        PostTraversal(cur->right, result);

        // 最后处理当前根节点
        result.push_back(cur->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        PostTraversal(root, result);

        return result;
    }
};

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
30
31
32
33
34
/**
 * 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 InTraversal(TreeNode *cur, vector<int> &result) {
        // 终止条件
        if (cur == nullptr) return;

        // 先处理左孩子
        InTraversal(cur->left, result);

        // 接着处理当前根节点
        result.push_back(cur->val);

        // 最后处理右孩子
        InTraversal(cur->right, result);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        InTraversal(root, result);

        return result;
    }
};

二叉树迭代遍历

前序遍历：使用栈实现

前序处理的方式是：根、左、右，因此向将根节点放入栈、右孩子进入栈、最后左孩子进入栈。

（注意这里为了减少将节点从栈中拿出还需要判断是否为空节点的操作，空结点不入栈，对应了上面的前序遍历第二种写法，在入栈前判断左右孩子是否为空）

一次循环所做的操作与一次递归函数基本类似，先处理从栈中取出的根节点，然后将右、左孩子入栈。

注意访问顺序和处理顺序，访问顺序就是第一次遇到这个节点，处理顺序是真正操作节点的值val。

访问和处理的顺序是一致的。前序遍历的访问顺序是中左右，处理的顺序也是中左右。

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
/**
 * 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> preorderTraversal(TreeNode* root) {
        stack<TreeNode *> st; // 用于存放节点
        vector<int> result;

        if (root) st.push(root);
        while (!st.empty()) {
            // 首先取出栈顶节点
            TreeNode *cur = st.top();
            st.pop();
            // 处理栈顶节点
            result.push_back(cur->val);

            // 访问左右孩子节点，注意顺序
            if (cur->right) st.push(cur->right);
            if (cur->left) st.push(cur->left);
        }

        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
/**
 * 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> inorderTraversal(TreeNode* root) {
        stack<TreeNode *> st; // 处理节点顺序
        vector<int> result;
        TreeNode *cur = root; // 访问节点顺序
        // 当访问节点为空并且栈空时所有节点都已处理
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) {
                // 当前访问节点不是空结点
                st.push(cur);
                // 继续向左访问
                cur = cur->left;
            } else {
                // 当前访问节点是空结点
                // 说明向左访问到头
                // 处理根节点
                cur = st.top();
                st.pop();
                result.push_back(cur->val);

                // 接着访问右孩子
                cur = cur->right;
            }
        } // end while

        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
/**
 * 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> postorderTraversal(TreeNode* root) {
        stack<TreeNode *> st;
        vector<int> result;
        if (root) st.push(root);
        while (!st.empty()) {
            TreeNode *cur = st.top();
            st.pop();
            // 处理顺序改为中、右、左
            result.push_back(cur->val);

            // 先左后右入栈，这样处理的时候就是先右后左
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
        }
        // 逆序处理
        reverse(result.begin(), result.end());

        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
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode *> st;
        vector<int> res;

        // 根节入栈
        if (root != nullptr) st.push(root);

        while (!st.empty()) {
            TreeNode *node = st.top();
			
            // 非空节点进行访问操作
            if (node != nullptr) {
                // 先将这个结点弹出
                st.pop();

                // 尝试将右孩子入栈
                if (node->right != nullptr) st.push(node->right);
                // 将中结点入栈，并且中间结点已经访问过，作为下一次处理的结点需要标记
                st.push(node);
                st.push(nullptr);

                // 最后将左孩子入栈
                if (node->left != nullptr) st.push(node->left);
            } else {
                // 如果栈顶是空指针，说明下一个是需要处理的结点
                st.pop();

                // 将需要处理的结点假如列表
                res.push_back(st.top()->val);
                st.pop();
            }
        }

        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
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        // 使用栈保存未访问的结点
        stack<TreeNode *>st;
        vector<int> res;

        if (root == nullptr) return res;
        // 首先将根结点入栈
        st.push(root);

        while (!st.empty()) {
            TreeNode *node = st.top();

            if (node != nullptr) {
                st.pop();

                // 右、左孩子入栈
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left);
                
                st.push(node);
                st.push(nullptr);
            } else {
                st.pop();
                res.push_back(st.top()->val);
                st.pop();
            }
        }

        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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        // 使用栈保存未访问的结点
        stack<TreeNode *>st;
        vector<int> res;

        if (root == nullptr) return res;
        // 首先将根结点入栈
        st.push(root);

        while (!st.empty()) {
            TreeNode *node = st.top();

            if (node != nullptr) {
                st.pop();
                st.push(node);
                st.push(nullptr);
                
                // 左、右孩子入栈
                if (node->left) st.push(node->left);
                if (node->right) st.push(node->right);
            } else {
                st.pop();
                res.push_back(st.top()->val);
                st.pop();
            }
        }

        return res;
    }
};

二叉树层序遍历

层序遍历就是每次从左到右遍历同一个深度的节点，类似于广度优先搜索，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

思路1：(类比于上面的迭代法中使用空指针作为标记)是为每层后面加一个空结点标识，当遇到空结点说明上一层处理完了，同时也要在队列中加一个空结点标识现在队列中是一层。

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        vector<int> temp;
        queue<TreeNode *> qu;
        // 每一层用一个空结点区分
        if (root != nullptr) {
            qu.push(root);
            qu.push(nullptr);
        } 
        
        while (qu.size() > 1 || qu.front() != nullptr) {
            // 取出队首元素
            TreeNode *node = qu.front();
            if (node != nullptr) {
                // 不为空层数不增加
                qu.pop();

                // 处理结点
                temp.push_back(node->val);

                // 并尝试将左右结点队
                if (node->left) qu.push(node->left);
                if (node->right) qu.push(node->right);
            } else {
                // 当队首元素为null说明这一层已经结束
                // 层数加1
                // 并且该层的孩子们（也就是下一层）也都入队，再加一个空结点
                qu.pop();
                res.push_back(temp);
                temp = vector<int>();
                qu.push(nullptr);
            }
        }
        if (temp.size() != 0) res.push_back(temp);

        return res;
    }
};

作者的思路1：（迭代法）当队列不为空时，每次处理一层，使在每次循环最开始记录当前队列多少元素，即为当前层数。然后使用for循环处理这size个结点即可。

还是一样空结点不入队，否则每次取出来节点还需要判断是否为空结点。

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
/**
 * 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) {
        queue<TreeNode *> que;
        vector<vector<int>> result;
        
        if (root) que.push(root);
        while (!que.empty()) {
            int nums_layer = que.size();
            // 处理这一层的所有节点
            vector<int> temp(nums_layer); // 该层所有节点
            for (int i = 0; i < nums_layer; i++) {
                // 取出节点
                TreeNode *cur = que.front();
                que.pop();

                // 处理节点
                temp[i] = cur->val;

                // 访问左右孩子
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            // 将该层结果保存
            result.push_back(temp);
        }

        return result;
    }
};

作者的思路2：使用深度优先遍历，递归的方式，每次处理完根节点之后，接着递归处理左右孩子。

递归参数：当前根结点，保存访问记录的列表，当前深度（因为一层使用一个列表表示，因此需要知道当前深度应该加到哪个列表中）

递归终止条件：当前根结点为空

一层递归逻辑：处理当前根结点，接着处理左右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth) {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

题目：

102.二叉树的层序遍历

与上面的代码一样

107.二叉树的层次遍历II

给你二叉树的根节点 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
/**
 * 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) {
        queue<TreeNode *> que;
        vector<vector<int>> result;
        // 层序遍历
        if (root) que.push(root);
        while (!que.empty()) {
            int layer_nums = que.size(); // 该层节点数目
            vector<int> layer_vals(layer_nums); // 当前一层所有节点
            for (int i = 0; i < layer_nums; i++) {
                TreeNode *cur = que.front();
                que.pop();
                // 处理当前根节点
                layer_vals[i] = cur->val;

                // 左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            // 将当前一层存储
            result.push_back(layer_vals);
        }
        reverse(result.begin(), result.end());

        return result;
    }
};

199.二叉树的右视图

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

199.tree 
1
2
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

思路：右视图就是层序遍历的每一层最后一个元素。

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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        // 层序遍历
        if (root)
            que.push(root);
        while (!que.empty()) {
            int layer_nums = que.size(); // 该层节点数目

            layer_nums--; // 剩余最后一个元素
            for (int i = 0; i < layer_nums; i++) {
                TreeNode* cur = que.front();
                que.pop();
                // 处理当前根节点
                // 什么都不做

                // 左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            // 将最后一个元素保留
            TreeNode* cur = que.front();
            que.pop();
            result.push_back(cur->val);
            // 左右孩子入队
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
        }

        return result;
    }
};

637.二叉树的层平均值

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

思路：层序遍历求每一层的平均值。

需要注意的是值的范围。

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
/**
 * 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) {
        queue<TreeNode *> que;
        vector<double> result;
        // 层序遍历
        if (root) que.push(root);
        while (!que.empty()) {
            int layer_nums = que.size(); // 该层节点数目
            double sum = 0; // 该层总和
            for (int i = 0; i < layer_nums; i++) {
                TreeNode *cur = que.front();
                que.pop();
                // 处理当前根节点
                sum += cur->val;

                // 左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            // 将当前一层平均值存储
            result.push_back(sum / layer_nums);
        }

        return result;
    }
};

429.N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

思路：与层序遍历基本相同，唯一区别是每个节点的孩子入队时，将N个节点都入队。

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node *> que;
        vector<vector<int>> result;
        // 层序遍历
        if (root) que.push(root);
        while (!que.empty()) {
            int layer_nums = que.size(); // 该层节点数目

            vector<int> layer_vals(layer_nums); // 当前一层所有节点
            for (int i = 0; i < layer_nums; i++) {
                Node *cur = que.front();
                que.pop();
                // 处理当前根节点
                layer_vals[i] = cur->val;

                // 所有孩子入队
                for (Node *child : cur->children) 
                    if (child) que.push(child);

            }
            // 将当前一层存储
            result.push_back(layer_vals);
        }

        return result;
    }
};

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

思路：层序遍历每一行求最大值。与求平均值类似。

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

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

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

116

思路：层序遍历会取出每一层所有的节点，因此除了对第一个的处理是保存当前next指针外，其余均零上一个的next指针指向自己并更新指针。每一层循环结束令最后一个节点的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
/*
// 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) que.push(root);
        // 层序遍历二叉树
        while (!que.empty()) {
            int layer_nums = que.size();
            
            // 对本层第一个特殊处理
            Node *cur = que.front();
            que.pop();
            Node **pre = &(cur->next); // 保存指向next指针的指针
            // 当前节点左右孩子入队
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
            --layer_nums;

            // 处理剩下的节点
            while (layer_nums--) {
                cur = que.front();
                que.pop();
                // 令前一个节点的next指针指向当前节点
                *pre = cur;
                // 更新前一个节点的next指针为当前节点的next指针
                pre = &(cur->next);

                // 当前节点左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            // 处理最后一个节点的next指针
            *pre = nullptr;
        }

        return root;
    }
};

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

给定一个二叉树：

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

思路：这道题与上一题的区别是：上一题是完美二叉树。对于完美二叉树来说，其节点位置都是可以预知的。本题使用层序遍历依然可解。

104.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思路：第一层也就是根节点所在一层的深度是1，下面每增加一层深度加1。其实可以看作是层序遍历的每一层的次数。因此每增加一层加1即可。

这里不再给出代码。

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路：上一题必须遍历完所有的节点才能知道谁是最远的叶子节点，该题层序遍历时由近及远进行遍历，只要当前层有叶子节点就可以提前返回当前层数。

具体实现就是：与上一题一样使用一个变量记录当前层数，然后在处理当前节点时，如果左右孩子均为空（说明是叶子节点）立即返回当前层数。

翻转二叉树

题目：226

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

226

思路：遍历左右结点，把节点的左右孩子互换即可。

层序遍历可以实现。

递归法：前序、后序遍历都可以，中序遍历不可以，这是因为中序先处理左孩子，再处理中间节点，处理中间结点时左右孩子互换，如果再处理右孩子那么右孩子是之前处理的左孩子。

迭代法：前、中、后序遍历都可以。这里的中序遍历可以是因为采用标记法处理节点时，即使处理的是中间节点，互换了左右孩子，下一次处理的节点是从栈中取出，不用担心因当前节点互换影响处理顺序。

这里给出迭代法的中序遍历。

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
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode *> st;
        if (root) st.push(root);

        // 采用中序法遍历
        // 应该处理的节点后面是一个空结点
        while (!st.empty()) {
            TreeNode *cur = st.top();
            st.pop();
            if (cur != nullptr) {
                // 如果不是空结点说明应该遍历
                if (cur->right) st.push(cur->right);

                // 添加中间节点和一个空结点
                // 表示下一次应该处理
                st.push(cur);
                st.push(nullptr);

                if (cur->left) st.push(cur->left);
            } else {
                // 如果是空结点说明栈顶是应该处理的节点
                cur = st.top();
                st.pop();
                // 交换左右节点
                swap(cur->left, cur->right);
            }
        }

        return root;
    }
};

阶段总结1

该部分首先介绍一下内容：

二叉树基本概念：包括满满二叉树、完全二叉树，以及二叉树的存储结构，定义方式等。

二叉树前中后递归遍历方法

二叉树前中后迭代遍历方法：由于中序遍历的访问和处理是不一致的（总是先访问到中间结点，才会访问左右孩子，但是处理的时候是先处理左孩子，再处理中间结点），所以需要一个标志（标识应该被处理）。后序遍历就是前序遍历稍微修改一下：中左右->中右左 这样范围访问之后再逆序即可。

二叉树前中后统一迭代遍历方法

二叉树层序遍历方法

对称二叉树

101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

（这里的意思其实就是检查一个二叉树是否关于中轴对称）

思路1：（递归法）不是比较左右结点，而是比较左右子树的外侧和里侧，令左子树的左孩子与右子树的右孩子比较，左子树的右孩子与右子树的左孩子比较。

递归的方式：

1.递归返回值和参数：参数为两个结点，返回值是bool

2.递归终止条件：这两个结点存在空结点的情况和不存在空结点的情况

3.递归的逻辑：首先排除两个树的根节点为空结点情况和均不是空结点但是不相等的情况，剩下的就是两个结点都不为空并且相等。接着外侧和里侧孩子进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    // 比较两个子树是否对称
    bool compare(TreeNode *left, TreeNode *right) {
        if (left == nullptr && right == nullptr) return true;
        else if (left != nullptr && right == nullptr) return false;
        else if (left == nullptr && right != nullptr) return false;
        else if (left->val != right->val) return false;

        // 比较完根节点之后开始比较孩子
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);

        return outside && inside;
    }

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return compare(root->left, root->right);
    }
};

思路2：（迭代法）使用队列，队列里面的每两个相邻的结点是要比较的两个结点。

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:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode *> que; // 队列
        if (root == nullptr) return true;
        que.push(root->left);
        que.push(root->right);
        // 队列中每两个为一组是需要进行比较的两个子树的根节点
        while (!que.empty()) {
            TreeNode *left = que.front(); que.pop();
            TreeNode *right = que.front(); que.pop();

            // 首先判断两个根节点是否满足条件
            if (left == nullptr && right == nullptr) continue;
            else if (left == nullptr && right != nullptr) return false;
            else if (left != nullptr && right == nullptr) return false;
            else if (left->val != right->val) return false;

            // 经过上面的判断之后此时可以确定两个子树的根节点不为空且val相等
            // 将需要进行比较的两个节点放在一起
            que.push(left->left);
            que.push(right->right);

            que.push(left->right);
            que.push(right->left);
        }

        return true;
    }
};

思路3：使用栈也是一样的。

题目：

100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路：采取相同的方式遍历两个树，依次比较两个节点

1.递归法：

递归的参数和返回值：参数为两个需要进行比较的树的根节点，返回值为bool

递归的终止条件：根节点进行比较，如果两个根节点都是空，那么返回true；如果一个为空另一个不为空，返回false；如果两个节点的值不同，返回空；剩下就是比较子树

递归逻辑：终止条件中已经比较了两个树的根，接下来分别比较左孩子和右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        else if (p != nullptr && q == nullptr) return false;
        else if (p == nullptr && q != nullptr) return false;
        else if (p->val != q->val) return false;

        // 经过上面的比较两个根已经相同
        // 比较两棵树的左孩子
        bool left_flag = isSameTree(p->left, q->left);
        bool right_flag = isSameTree(p->right, q->right);

        return left_flag && right_flag;
    }
};

2.迭代法：使用一个队列保存每次需要进行比较的两个节点。

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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode *> que;
        que.push(p);
        que.push(q);
        // 每次分别迭代两棵树的一个节点
        while (!que.empty()) {
            TreeNode *left_node = que.front(); que.pop();
            TreeNode *right_node = que.front(); que.pop();

            if (left_node == nullptr && right_node == nullptr) continue;
            else if (left_node != nullptr && right_node == nullptr) return false;
            else if (left_node == nullptr && right_node != nullptr) return false;
            else if (left_node->val != right_node->val) return false;

            // 经过上面的比较两个节点已经相同
            // 遍历各自的左孩子
            que.push(left_node->left);
            que.push(right_node->left);

            // 遍历各自的右孩子
            que.push(left_node->right);
            que.push(right_node->right);
        }

        return true;
    }
};

572.另一个树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路1：遍历root的每一个节点，分别作为子树，与subRoot进行比较。

两颗子树进行比较的方法在上一题中已经给出，因此这里只需要在外层增加遍历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
50
51
52
53
class Solution {
public:
    // 判断两棵树是否完全相同
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode *> que;
        que.push(p);
        que.push(q);
        // 每次分别迭代两棵树的一个节点
        while (!que.empty()) {
            TreeNode *left_node = que.front(); que.pop();
            TreeNode *right_node = que.front(); que.pop();

            if (left_node == nullptr && right_node == nullptr) continue;
            else if (left_node != nullptr && right_node == nullptr) return false;
            else if (left_node == nullptr && right_node != nullptr) return false;
            else if (left_node->val != right_node->val) return false;

            // 经过上面的比较两个节点已经相同
            // 遍历各自的左孩子
            que.push(left_node->left);
            que.push(right_node->left);

            // 遍历各自的右孩子
            que.push(left_node->right);
            que.push(right_node->right);
        }

        return true;
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        queue<TreeNode *> que;
        if (root) que.push(root); // 空结点不入栈

        // 层序遍历
        while (!que.empty()) {
            int layer_size = que.size(); // 本层节点个数
            // 访问本层所有节点
            while (layer_size--) {
                TreeNode *cur = que.front(); que.pop();

                // 访问节点
                if (isSameTree(cur, subRoot)) return true;

                // 左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }

        return false;
    }
};

思路2：不管是使用哪种方式遍历树，实际上最终把每个节点都访问一次，因此可以将树看作是一个节点序列；

采用同样的方式遍历subRoot，那么subRoot也是一个序列。

因此这里就相当于判断subRoot是否为root序列的一个子序列，类似于字符串的模式匹配，可以采用KMP算法。

二叉树的最大深度

题目：104、

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思路1：递归法，

前序遍历递归法

1.递归的参数、返回值：参数是当前子树的根节点，和当前子树根节点的深度，即根节点到当前子树根节点的节点数。无返回值

2.递归的终止条件：当遇到空结点时，返回

3.递归的逻辑：在最开始应该使用一个全局变量记录最大深度，然后判断当前递归传进来的参数（即当前子树根节点的深度是否为更大的深度），然后尝试递归左孩子和右孩子

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
class Solution {
public:
    int result;

    void GetDepth(TreeNode *cur, int depth) {
        // 比较当前子树节点的深度是否更大
        result = result > depth ? result : depth;

        // 递归终止
        if (cur->left == nullptr && cur->right == nullptr) return;

        // 递归左孩子
        if (cur->left) {
            depth++; // 加上左孩子深度加1
            GetDepth(cur->left, depth);
            depth--; // 回溯到当前子树根节点深度减1
        }

        if (cur->right) {
            depth++;
            GetDepth(cur->right, depth);
            depth--;
        }
    }

    int maxDepth(TreeNode* root) {
        result = 0;

        // 递归中空结点不进行递归
        if (root == nullptr) return result;

        GetDepth(root, 1);

        return result;
    }
};

后序遍历递归法：

1.递归的参数、返回值：参数是当前子树根节点，返回值是当前子树根节点的高度

2.递归的终止条件：当前传入的根节点为空时，返回0

3.递归的处理逻辑：先求左子树的高度，再求右子树的高度，然后当前子树的高度是二者中较大的加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int GetDepth(TreeNode *cur) {
        if (cur == nullptr) return 0;

        int left_depth = GetDepth(cur->left);
        int right_depth = GetDepth(cur->right);

        return max(left_depth, right_depth) + 1;
    }

    int maxDepth(TreeNode* root) {
        return GetDepth(root);
    }
};

思路2：迭代法（使用层序遍历比较简单）

遍历时记录每一层的高度

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) {
        queue<TreeNode *> que; // 存放未访问节点
        if (root) que.push(root); // 空结点不入队
        int depth = 0;
        
        while (!que.empty()) {
            // 此为新的一层
            depth++;

            // 记录该层节点数
            int layer_size = que.size();
            for (int i = 0; i < layer_size; i++) {
                // 取出节点
                TreeNode *cur = que.front();
                que.pop();

                // 尝试左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        } // end when queue is empty

        return depth;
    }
};

收获：

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度（前序遍历记录的是根节点到当前节点的路径条数或者节点数），使用后序求的是高度（后序遍历记录的是从叶子节点到当前节点的路径书或者节点数）。

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

所以根节点的高度就是二叉树的最大深度

题目：559 N 叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

思路：与二叉树基本一致。下面只使用层序遍历的迭代法实现。

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 maxDepth(Node* root) {
        queue<Node *> que; // 保存未“访问”的节点
        if (root != nullptr) que.push(root);
        int depth = 0;

        // 遍历以及处理所有的节点
        while (!que.empty()) {
            // 此为新的一层
            depth++;

            // 获取当前层节点数
            int layer_size = que.size();
            for (int i = 0; i < layer_size; i++) {
                // 取出当前节点
                Node *cur = que.front();
                que.pop();

                // 将所有孩子都入队
                for (int j = 0; j < cur->children.size(); j++) {
                    if (cur->children[j] != nullptr)
                        que.push(cur->children[j]);
                }
            }
        } // end when que is empty

        return depth;
    }
};

二叉树的最小深度

题目：111

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路1：递归法

前序遍历从根节点记录深度，所以这里的递归使用前序。

1.递归的参数、返回值：参数是当前根节点，以及从根节点到当前根节点的节点数。无返回值

2.递归的终止条件：空结点不进行递归，所以这里不需要终止条件

3.递归的逻辑：首先判断该节点是否为叶子节点，如果是则记录此时深度并返回；然后尝试递归左孩子，接着尝试递归右孩子

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

    void PreTraversal(TreeNode *cur, int depth) {
        if (cur->left == nullptr && cur->right == nullptr) {
            min_depth = min_depth > depth ? depth : min_depth;
            return;
        }

        // 尝试左孩子
        if (cur->left) PreTraversal(cur->left, depth + 1);
        // 尝试右孩子
        if (cur->right) PreTraversal(cur->right, depth + 1);
    }

    int minDepth(TreeNode* root) {
        // 空指针不递归
        if (root == nullptr) return 0;

        min_depth = INT_MAX;

        PreTraversal(root, 1);

        return min_depth;
    }
};

如果使用后序遍历：后序遍历记录的是子树的最小深度

题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

什么是叶子节点，左右孩子都为空的节点才是叶子节点！

如果采用以下递归逻辑：

1
2
3
4
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

那么如果一个结点没有左孩子，那么没有左孩子的分支就会作为最小深度。

正确逻辑应该是：

如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。

最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

思路2：使用迭代方式的层序遍历。只要遇到左右孩子为空的就输出深度。

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:
    int minDepth(TreeNode* root) {
        queue<TreeNode *> que; // 保存未“访问”的节点
        if (root != nullptr) que.push(root);

        int depth = 0;
        
        while (!que.empty()) {
            // 此为新的深度
            depth++;

            // 当前一层节点数
            int layer_size = que.size();
            for (int i = 0; i < layer_size; i++) {
                // 获取节点
                TreeNode *cur = que.front();
                que.pop();

                if (cur->left == nullptr && cur->right == nullptr) return depth;

                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        } // 当队列为空终止

        return depth;
    }
};

完全二叉树的节点个数

题目：222

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

思路1：遍历所有节点统计个数，可以采用递归或者迭代法。

代码略。

作者的思路：采用完全二叉树的思路：需要判断是否为满二叉树（根据左右结点深度是否一致，左子树一直遍历左节点，右子树一直遍历右节点）

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：

img

在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树，如图：

img

如果是满二叉树，就根据公式计算这个完全二叉树的结点数并返回， 2^树深度 - 1 ；

如果不是满二叉树，那就接着遍历返回左右子树的结点数之和+根节点的数量1

1.递归参数和返回值：参数为当前子树节点，返回值是当前子树节点的节点数

2.递归的终止条件：空结点不进行递归

3.递归的逻辑：使用while循环求当前节点左子树和右子树的深度，然后判断深度是否一致。

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

        // 求左子树和右子树的深度
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        int left_h = 0;
        int right_h = 0;

        while (left) {
            left = left->left;
            left_h++;
        }
        while (right) {
            right = right->right;
            right_h++;
        }
        
        // 如果左子树左深度等于右子树右深度
        if (left_h == right_h) return (2 << left_h) - 1;
        else return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

时间复杂度：O(log n × log n)，

空间复杂度：O(log n)，递归的调用栈

平衡二叉树

题目：110

给定一个二叉树，判断它是否是 平衡二叉树

明确概念：

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

在题目求二叉树最大深度时采用的是后序遍历，求的是根节点的高度，也就是高度。

思路1：递归。平衡二叉树就是左右子树高度不能相差1，因此采用后序遍历。

1.递归的参数和返回值：参数是一个子树根结点，返回值是子树高度，如果不是平衡子树就返回-1

2.递归的终止：当遇到空结点时。

3.递归的逻辑：求左右子树高度，注意这里如果子树高度为-1，说明子树不是平衡的，那么以这个根节点的树也不是平衡的。

判断左右子树高度是否相差1以内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int CountHeight(TreeNode *cur) {
        // 递归终止
        if (cur == nullptr) return 0;

        // 求左右子树高度
        // 如果某一棵左右子树不平衡则该子树页不平衡
        int left_h = CountHeight(cur->left);
        if (left_h == - 1) return -1;
        int right_h = CountHeight(cur->right);
        if (right_h == -1) return -1;
        
        
        if (abs(left_h - right_h) > 1) return -1;
        else return max(left_h, right_h) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if (CountHeight(root) != -1) return true;
        else return false;
    }
};

思路2：迭代法：使用一个函数计算当前节点的深度，然后使用后序遍历判断每个节点的左右子树深度是否一致。

存在很多冗余计算，因此复杂度很高。

二叉树的所有路径

题目：257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

思路：前序遍历可以记录从根节点到相应节点的路径，同时这里明显有回溯的操作，遍历完左孩子之后还需要删除左孩子，然后添加右孩子，所以使用递归更方便。

1.递归的参数和返回值：参数为当前根节点，一个用于装目前路径的数组path。无返回值

2.递归的终止条件：空节点不会进入递归

3.递归的逻辑：先将当前根节点加入路径，然后判断当前根节点左右孩子是否为空，如果为空说明遇到叶子节点，应该记录此时路径。尝试遍历左孩子，注意会将左孩子加入节点，尝试完毕之后需要弹出左孩子。右孩子同理。

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
class Solution {
public:
    vector<string> result;
    void PreTraversal(TreeNode *cur, vector<int> &path) {
        // 空结点不进入递归
        // 先将当前根节点加入路径
        path.push_back(cur->val);

        // 判断左右孩子是否都为空
        if (cur->left == nullptr && cur->right == nullptr) {
            // 将路径转换为string
            string tmp;
            for (int i = 0; i < path.size()-1; i++) {
                tmp += to_string(path[i]);
                tmp += "->";
            }
            tmp += to_string(path[path.size()-1]);
            result.push_back(tmp);
        }

        // 尝试遍历左孩子
        if (cur->left) {
            PreTraversal(cur->left, path);
            // 回溯
            path.pop_back();
        }
        // 尝试遍历右孩子
        if (cur->right) {
            PreTraversal(cur->right, path);
            path.pop_back();
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        // 空结点不进行递归
        if (root == nullptr) return result;

        vector<int> path;
        PreTraversal(root, path);

        return result;
    }
};

思路2：使用迭代，一个栈用于模拟前序遍历，一个栈用于装从根结点到当前节点的路径。

阶段总结2

对称二叉树：递归比较两个子树的外侧和内侧，或者迭代每次处理对应的两个节点。

二叉树最大深度：深度指的是从根节点到当前节点的结点个数（适合使用前序遍历，因为首先处理处理当前结点深度），高度指的是从当前结点到叶子结点的结点个数（适合后序遍历，先处理子树的高度再处理根的高度）

二叉树最小深度：需要注意的是深度指的是到叶子结点，即左右孩子结点都为空。

完全二叉树结点数量：采用递归方式，如果是满二叉树，即左孩子一直向左遍历的深度和右孩子一直向右遍历的深度一样，就利用公式计算，否则就统计左右孩子加上根节点。

是否为平衡二叉树：递归求左右孩子的高度，判断是否相差1

找寻所有路径：前序遍历递归

左叶子之和

题目：404

给定二叉树的根节点 root ，返回所有左叶子之和。

思路：判断一个节点是否为左叶子，需要知道父节点和左右孩子节点为空。这里选择在“父节点”这一层判断左孩子是否为叶子节点。

递归法：

1.递归的参数和返回值：参数是当前子树根节点，无返回值

2.递归的终止条件：空节点不递归

3.递归的逻辑：处理当前根节点：判断左孩子是否为空，如果不为空，判断左孩子是否为叶子节点，如果是，累加和；
接着尝试递归左孩子和右孩子（空结点不递归）

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
class Solution {
public:
    int result;

    void PreTraversal(TreeNode *cur) {
        // 空结点不递归

        // 首先判断左孩子是否为叶子
        if (cur->left && !cur->left->left && !cur->left->right)
            result += cur->left->val;
        
        // 尝试递归左孩子和右孩子
        if (cur->left) PreTraversal(cur->left);
        if (cur->right) PreTraversal(cur->right);
    }

    int sumOfLeftLeaves(TreeNode* root) {
        result = 0;
        // 空结点不递归
        if (root == nullptr) return 0;
        PreTraversal(root);

        return result;
    }
};

迭代法：略

找树左下角的值

题目：513

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例：

513 
1
2
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

思路1：迭代法考虑层序遍历，最后一层的第一个元素就是答案。

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 findBottomLeftValue(TreeNode* root) {
        queue<TreeNode *> que;
        // 空结点不入队
        if (root == nullptr) exit(1);

        que.push(root);
        int result;
        // 层序遍历
        while (!que.empty()) {
            // 当前层的节点数
            int layer_size = que.size();

            // 记录本层第一个元素的值
            result = que.front()->val;
            for (int i = 0; i < layer_size; i++) {
                // 获取当前节点
                TreeNode *cur = que.front();
                que.pop();

                // 尝试左右孩子入队
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }

        return result;
    }
};

思路2：递归法：最下层的深度一定是最大的。因此采用前序遍历，一边遍历一边记录深度。只有当前深度大于记录深度时才更新result并且更新最大深度。

1.递归的参数和返回值：参数是当前子树根节点，和当前子树根节点的深度；无返回值

2.递归的终止条件：空结点不进入递归，当前节点为叶子节点时尝试更新深度和记录节点，最后返回；

3.递归逻辑：在判断终止之后，尝试递归左孩子和右孩子。（空节点不递归）

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
class Solution {
public:
    int result;
    int max_depth;

    void PreTraversal(TreeNode *cur, int depth) {
        // 判断当前节点是否为叶子节点
        if (cur->left == nullptr && cur->right == nullptr) {
            if (depth > max_depth) {
                result = cur->val;
                max_depth = depth;         
            }
            // 只要是叶子节点就返回
            return;
        }

        // 尝试递归左孩子
        if (cur->left) PreTraversal(cur->left, depth + 1);
        // 尝试递归右孩子
        if (cur->right) PreTraversal(cur->right, depth + 1);
    }

    int findBottomLeftValue(TreeNode* root) {
        // 空结点不递归
        if (!root) exit(1);

        // 至少一个节点
        max_depth = 0;
        PreTraversal(root, 1);

        return result;
    }
};

路径总和（递归什么时候需要返回）

题目：112

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

思路1：递归法，需要记录从根节点到叶子节点的路径和，所以尝试使用先序遍历。

1.递归的参数和返回值：参数是当前子树根节点、从跟接待你到当前节点的路径和、目标值，返回值是能够满足路径和。

2.递归的终止条件：空结点不递归，如果遇到叶子节点就判断路径和是否满足，如果满足就返回true，否则返回false

3.递归的逻辑：在上面的判断之后，尝试遍历左孩子和右孩子（空结点不递归），返回值是左递归 || 右递归

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:
    bool PreTraversal(TreeNode *cur, int path, int targetSum) {
        // 空结点不递归

        // 判断当前节点是否为叶子节点
        if (cur->left == nullptr && cur->right == nullptr) {
            if (path == targetSum) return true;
            else return false;
        }

        // 尝试递归左右孩子
        bool left_flag = false, right_flag = false;
        if (cur->left) left_flag = PreTraversal(cur->left, path + cur->left->val, targetSum);
        // 如果提前发现路径可以不再递归
        if (left_flag) return true;

        if (cur->right) right_flag = PreTraversal(cur->right, path + cur->right->val, targetSum);
        if (right_flag) return true;

        // 前面都没有返回说明没有找到
        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        // 空结点不递归
        if (!root) return false;

        int path = root->val;
        return PreTraversal(root, path, targetSum);
    }
};

思路2：迭代法，使用一个栈来实现前序遍历，使用另一个栈保存从根节点到栈顶节点的路径和。

在循环中处理栈顶节点，先判断是否为叶子节点，如果是叶子节点就比较路径和；否则尝试右左孩子入栈以及右左孩子的路径和。

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
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        stack<TreeNode *> tree_st;
        stack<int> path_st; // 保存到栈顶节点的路径和
        // 空结点不入栈
        if (!root) return false;
        tree_st.push(root);
        path_st.push(root->val);

        // 前序遍历
        while (!tree_st.empty()) {
            // 取出待处理元素
            TreeNode *cur = tree_st.top();
            tree_st.pop();
            // 取出从根到栈顶节点的路径和
            int path = path_st.top();
            path_st.pop();

            // 判断当前节点是否为叶子节点
            if (!cur->left && !cur->right) {
                if (path == targetSum) return true;
                else continue;
            }

            // 尝试右、左孩子入栈
            if (cur->right) {
                tree_st.push(cur->right);
                path_st.push(path + cur->right->val);
            }
            if (cur->left) {
                tree_st.push(cur->left);
                path_st.push(path + cur->left->val);
            }
        }

        return false;
    }
};

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

如果需要搜索整棵二叉树（中某个节点）且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
如果需要搜索整棵二叉树（中某个节点）且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先中介绍）
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

题目： 113.路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

思路1：递归法，前序遍历方便记录从根节点到当前节点的路径。

1.递归的参数和返回值：参数是当前节点、从跟节点到当前节点的路径（作为全局变量）、（目标和-从根节点到当前节点的路径和）；无返回值

2.递归的终止条件：空结点不进入递归

3.递归的逻辑：判断当前结点是否为叶子节点，如果是则判断此时传入的参数是否为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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void PreTraversal(TreeNode *cur, int target) {
        // 空结点不递归
        
        // 判断是否为叶子节点
        if (!cur->left && !cur->right) {
            if (target == 0) result.push_back(path);
            // 只要是叶子节点就可以返回
            return; 
        }

        // 尝试递归左右孩子
        if (cur->left) {
            path.push_back(cur->left->val);
            PreTraversal(cur->left, target - cur->left->val);
            // 回溯
            path.pop_back();
        }
        if (cur->right) {
            path.push_back(cur->right->val);
            PreTraversal(cur->right, target - cur->right->val);
            path.pop_back();
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        // 空结点不递归
        if (root == nullptr) return result;

        path.push_back(root->val);
        PreTraversal(root, targetSum - root->val);

        return result;
    }
};

思路2：递归法：使用一个栈用来前序遍历，使用另一个栈保存从根节点到栈顶节点的路径，使用一个栈保存从根节点到栈顶节点的路径和。

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
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        stack<TreeNode *> node_st;
        stack<vector<int>> paths; // 从根节点到栈顶节点的路径
        stack<int> path_st; // 记录从根节点到栈顶节点的路径和
        
        vector<vector<int>> result;
        // 空结点不入栈 
        if (!root) return result;
        node_st.push(root);
        paths.push(vector<int>{root->val}); // 记录路径
        path_st.push(root->val);
        // 前序遍历
        while (!node_st.empty()) {
            // 取出当前节点
            TreeNode *cur = node_st.top();
            node_st.pop();
            // 取出当前路径和
            int path_sum = path_st.top();
            path_st.pop();
            // 取出当前路径
            vector<int> path = paths.top();
            paths.pop();

            // 判断当前节点是否为叶子
            if (!cur->left && !cur->right) {
                if (path_sum == targetSum) result.push_back(path);
                // 不管是否满足条件，只要是叶子节点就可以跳过剩余
                continue;
            }

            // 尝试右、左孩子
            if (cur->right) {
                // 将右孩子加入路径
                path.push_back(cur->right->val);
                paths.push(path);

                // 将右孩子的路径和加入
                path_st.push(path_sum + cur->right->val);
                // 将右孩子入栈
                node_st.push(cur->right);


                // 回溯
                path.pop_back();
            }
            if (cur->left) {
                path.push_back(cur->left->val);
                paths.push(path);

                path_st.push(path_sum + cur->left->val);
                node_st.push(cur->left);

                // 回溯
                path.pop_back();
            }
        }

        return result;
    }
};

从中序与后序遍历序列构造二叉树

  • 106.从中序与后序遍历序列构造二叉树

  • 105.从前序与中序遍历序列构造二叉树

    题目：106

    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

    分析：

    对于两个数组，后序遍历数组的最后一个元素是根节点，在中序遍历数组中找到这个元素，这个元素前面的是左子树的中序遍历，后面的是右子树的中序遍历。统计左子树中序遍历的元素个数k，后序遍历数组的元素[0, k - 1]就是左子树的后序遍历，元素[k, size - 1]就是右子树的后序遍历。

    创建当前根节点，然后左子树和右子树分别指向两个构建的子树。

    思路1：递归法，

    1.递归的参数和返回值：参数：总的中序和后序数组，当前子树的中序范围，后序范围，范围使用左闭右开表示法[start, end)；返回值是当前子树根节点

    2.递归的终止条件：如果范围内的元素为0则返回空指针

    3.递归的逻辑：首先，后序范围内的最后一个元素是根；然后，尝试在中序范围内找到这个根元素，根元素之前时左子树的中序，根元素之后是右子树的中序；接着，根据左子树中序元素个数确定左子树后序范围，以及右子树后序范围；最后，创建根节点并令根节点等于左子树和右子树递归返回的节点。

    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
    class Solution {
    public:
        TreeNode * BuildCore(vector<int> &inorder, int in_start, int in_end,
                             vector<int> &postorder, int post_start, int post_end) {
            // 终止条件
            if (in_end == in_start) return nullptr;

            // 根节点是后序遍历的最后一个元素
            int root_val = postorder[post_end - 1];
            TreeNode *root = new TreeNode(root_val);

            // 在中序范围中查找根节点值的下标
            int root_index = in_start;
            while (inorder[root_index] != root_val && root_index < in_end) root_index++;
            // 如果没找到报错
            if (root_index == in_end) exit(1);

            // 循环结束找到根节点在中序的下标
            // 确定左子树节点数
            int k = root_index - in_start;
            
            // 递归左子树
            root->left = BuildCore(inorder, in_start, root_index,
                                   postorder, post_start, post_start + k);
            // 递归右子树
            root->right = BuildCore(inorder, root_index + 1, in_end,
                                    postorder, post_start + k, post_end - 1);
            
            return root;
        }


        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            // 错误检查
            if (inorder.size() != postorder.size()) exit(2);

            int len = postorder.size();

            return BuildCore(inorder, 0, len, postorder, 0, len);
        }
    };

    题目：105

    同理，都是根据前序遍历找到根，再通过中序遍历确定左右子树。

最大二叉树

题目：654

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

分析：

与上一题思路类似，都是先确定根节点位置，然后分成左右子树。这里选择采用递归实现，因为比较清晰。

1.递归的参数和返回值：参数是数组、范围（范围是左开右闭[start, end)），返回值是以范围构建的树；

2.递归的终止条件：当start == end时，应该返回空指针

3.递归的逻辑：首先采取一个时间复杂度为O(n)的方式找到最大值的下标，以最大值创建根节点；然后递归的分别以左边和右边创建子树。

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:
    TreeNode *BuildCore(vector<int> &nums, int start, int end) {
        // 判断是否为空
        if (start == end) return nullptr;

        // 首先遍历找到最大值的下标
        int max_index = start;
        for (int i = start + 1; i < end; i++) {
            if (nums[max_index] < nums[i]) max_index = i;
        }

        // 以最大值创建根节点
        TreeNode *root = new TreeNode(nums[max_index]);

        // 划分左右边界并递归创建左子树和右子树
        root->left = BuildCore(nums, start, max_index);
        root->right = BuildCore(nums, max_index + 1, end);

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int nums_size = nums.size();
        return BuildCore(nums, 0, nums_size);
    }
};

阶段总结3

左叶子之和：判断一个左叶子必须根据一个根结点来判断，即左孩子存在，且左孩子是一个叶子节点（没有左右孩子）。

左下角的值：迭代法采用层序很好理解；递归法需要采用一个变量记录最大深度，第一次到达最大深度时并且为叶子结点就是最左。

路径总和：使用一个全局变量记录从根节点到当前节点的路径，需要注意的是，在递归左孩子返回之后需要将path回溯，即删除左孩子才能去遍历右孩子。另外需要关注的是递归什么时候需要返回：

如果需要搜索整棵二叉树（中某个节点）且不用处理递归返回值，递归函数就不要返回值。（113.路径总和ii）
如果需要搜索整棵二叉树（中某个节点）且需要处理递归返回值，递归函数就需要返回值。 （236. 二叉树的最近公共祖先中介绍）
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112.路径总和）

中序遍历和后序遍历、中序遍历和前序遍历构建二叉树：实际上是先根据前序遍历或者后序遍历确定根的位置，然后在中序遍历中找到根，划分为左右子树，然后递归的对左右子树进行操作。

最大二叉树：与上面类似，先找到最大值作为根，然后划分为左右子树，再继续递归创建。

合并二叉树

题目：617

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例：

617 
1
2
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

分析：

思路1：递归法

同时遍历两个树tree1和tree2，如果两个都为空结点，则返回空结点；如果其中一个为空结点，则对复制非空节点，并令复制的节点等于对非空节点的左右孩子递归的返回值；如果都不为空，则创建一个新节点等于两个子树根节点的和，然后令新节点的左右孩子等于递归调用的返回值。

1.递归的参数：两个子树根节点；返回值是合并之后的根节点

2.递归的终止：当两个子树都为空指针时，返回空指针；

3.递归的逻辑：如果其中一个为空指针而另一个不为空，那么创建一个新节点值为非空结点的值，然后以（空指针，非空节点左孩子）和（空指针，非空节点右孩子）的方式递归，令新节点的左右孩子接收递归的返回值；如果两个树都不为空，那么创建一个新节点的值等于二者之和，然后以（tree1的左孩子，tree2的左孩子）和（tree1的右孩子，tree2的右孩子）的方式递归，令新节点的左右孩子接收递归的返回值。

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
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 递归终止条件
        if (root1 == nullptr && root2 == nullptr) return nullptr;

        // 只要不是全为空就需要创建一个新节点
        TreeNode *new_root = new TreeNode;

        // 如果其中一个为空
        if (root1 == nullptr && root2 != nullptr) {
            // 新节点的值
            new_root->val = root2->val;
            // 左孩子接收递归
            new_root->left = mergeTrees(nullptr, root2->left);
            // 右孩子接收递归
            new_root->right = mergeTrees(nullptr, root2->right);
        } else if (root1 != nullptr && root2 == nullptr) {
            // 新节点的值
            new_root->val = root1->val;
            // 左孩子接收递归
            new_root->left = mergeTrees(root1->left, nullptr);
            // 右孩子接收递归
            new_root->right = mergeTrees(root1->right, nullptr);
        } else {
            new_root->val = (root1->val + root2->val);
            new_root->left = mergeTrees(root1->left, root2->left);
            new_root->right = mergeTrees(root1->right, root2->right);
        }

        return new_root;
    }
};

思路2：迭代法

需要同时比较的是两个节点，可以使用一个队列保存节点，每两个为一组是需要处理的节点。由于没有递归，无法将每次循环的节点作为参数返回，需要记录上一次循环的节点的左右孩子指针，所以这里选择使用一个队列，保存指向节点指针的指针。

每次循环取出两个节点之后，判断是否都为空，如果都为空则跳过剩余操作；如果其中一个为空而另一个不为空，则创建一个新节点，令其值等于非空节点的值，并将（空指针，非空节点左孩子）和（空指针，非空节点右孩子）成对入队，另外需要将新节点的左右孩纸指针的指针入另一个队。如果都不为空，处理方式类似。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        queue<TreeNode *> que1; // 保存的是节点
        queue<TreeNode **> que2; // 保存的是指向节点指针的指针
        
        que1.push(root1);
        que1.push(root2);
        // 创建一个虚拟根节点
        TreeNode *v_root = new TreeNode;
        // 将虚拟根节点的“左孩子”的指针入队
        que2.push(&v_root->left);

        // 每次处理que1的前两个节点
        while (!que1.empty()) {
            // 取出两个根节点
            TreeNode *tree1 = que1.front();
            que1.pop();
            TreeNode *tree2 = que1.front();
            que1.pop();
            // 取出指向上一层根节点的孩子指针的指针
            TreeNode **tmp = que2.front();
            que2.pop();

            // 创建一个新节点
            TreeNode *new_node = new TreeNode;
            // 判断是否都为空指针
            if (tree1 == nullptr && tree2 == nullptr) {
                // 删除新建的节点
                delete new_node;
                // 返回空指针
                new_node = nullptr;
            } else if (tree1 != nullptr && tree2 == nullptr) {
                // 新节点的值
                new_node->val = tree1->val;
                // 将左孩子和空指针入队
                que1.push(tree1->left);
                que1.push(nullptr);
                // 将指向新节点的左孩子的指针入队
                que2.push(&(new_node->left));

                // 将右孩子和空指针入队
                que1.push(tree1->right);
                que1.push(nullptr);
                que2.push(&(new_node->right));
            } else if (tree1 == nullptr && tree2 != nullptr) {
                // 新节点的值
                new_node->val = tree2->val;
                // 将空指针和左孩子入队
                que1.push(nullptr);
                que1.push(tree2->left);
                // 将指向新节点的左孩子的指针入队
                que2.push(&(new_node->left));

                // 将空指针和右孩子入队
                que1.push(nullptr);
                que1.push(tree2->right);
                que2.push(&(new_node->right));
            } else {
                // 新节点的值
                new_node->val = (tree1->val + tree2->val);
                // 将左孩子入队
                que1.push(tree1->left);
                que1.push(tree2->left);
                // 将指向新节点的左孩子的指针入队
                que2.push(&(new_node->left));

                // 将右孩子入队
                que1.push(tree1->right);
                que1.push(tree2->right);
                que2.push(&(new_node->right));
            }

            // 令指向上一次循环的新节点的左或右孩子的指针指向当前的新节点
            *tmp = new_node;
        }

        // 删除虚拟根节点
        TreeNode *de = v_root;
        v_root = v_root->left;
        delete de;

        return v_root;
    }
};

搜索二叉树中的搜索（二叉搜索树）

二叉搜索树是一个有序树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

另外，如果采用中序遍历，那么二叉搜索树一定是一个有序序列。

题目：700.

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

分析：

由于二叉搜索树的性质，将目标值与当前根节点的值进行比较，如果目标值等于根节点，说明已经找到了；如果目标值较大，那么应该向右子树去寻找；如果目标值较小，那么应该向左子树去寻找。

思路1：递归法

1.递归的参数和返回值：参数是当前子树和目标值；返回值是和目标值相等的节点。

2.递归的终止条件：空结点返回nullptr （空结点进入递归）

3.递归的逻辑：与上面分析一致。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return nullptr;

        // 与当前根节点进行比较
        if (root->val == val) return root;
        else if (root->val < val) return searchBST(root->right, val);
        else return searchBST(root->left, val);
    }
};

思路2：迭代法

使用一个队列保存节点，每次循环处理当前节点，如果刚好等于就返回；如果目标值较大，就将右孩子入队；否则左孩子入队。

注意，这里空指针可以入队。循环时遇到空指针直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        queue<TreeNode *> que;
        que.push(root);

        while (!que.empty()) {
            // 取出当前节点
            TreeNode *cur = que.front();
            que.pop();

            if (cur == nullptr) return nullptr;

            if (cur->val == val) return cur;
            else if (cur->val < val) que.push(cur->right);
            else que.push(cur->left);
        }

        return nullptr;
    }
};

采用迭代的方式，一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。但是因为二叉树搜索树是有顺序的，所以直接根据值判断需要放的结点是左子树还是右子树即可。

验证二叉搜索树

题目：98.

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

分析：

思路1：递归法，想要判断当前子树是否合法，那么需要左子树合法，并且右子树合法，以及左子树的最大值小于当前根的值，右子树的最小值大于当前根的值。

1.递归的参数：根节点；返回值：[true or false, 子树最大值，子树最小值]

2.递归的终止条件：空结点不递归；遇到叶子节点返回[true, 叶子节点的值,叶子节点的值]

3.递归的逻辑：先递归左孩子，然后递归右孩子，最后根据返回值判断是否合法。

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
69
70
71
class Solution {
public:
    vector<int> PostTraversal(TreeNode *cur) {
        // 创建一个用于返回的数组
        vector<int> result{0, 0, 0}; // [T or F, 子树最小值, 子树最大值]
        // 如果当前节点是叶子节点
        if (!cur->left && !cur->right) {
            result = vector<int>{1, cur->val, cur->val};
            return result;
        }

        if (cur->left != nullptr && cur->right == nullptr) {
            // 如果只有左孩子
            vector<int> left = PostTraversal(cur->left);
            // 根据左孩子返回的结果进行判断
            if (left[0] == 0 || left[2] >= cur->val) {
                // 如果左子树不合法或者左子树最大值大于当前根的值
                // 则当前数不合法
                result[0] = 0;
            } else {
                result[0] = 1;
                result[1] = left[1];
                result[2] = cur->val;
            }
        } else if (cur->left == nullptr && cur->right != nullptr) {
            // 如果只有右孩子
            vector<int> right = PostTraversal(cur->right);
            // 根据左孩子返回的结果进行判断
            if (right[0] == 0 || right[1] <= cur->val) {
                // 如果左子树不合法或者左子树最大值大于当前根的值
                // 则当前数不合法
                result[0] = 0;
            } else {
                result[0] = 1;
                result[1] = cur->val;
                result[2] = right[2];
            }
        } else {
            // 如果两个孩子都存在
            vector<int> left = PostTraversal(cur->left);
            vector<int> right = PostTraversal(cur->right);

            // 根据左子树和右子树返回的结果进行判断
            if (left[0] == 0 || right[0] == 0) {
                // 如果有一颗子树不是合法二叉树
                // 则该树也不是合法二叉树
                result[0] = 0;
            } else if (left[2] >= cur->val || right[1] <= cur->val) {
                // 如果左子树最大值大于当前根，或右子树最小值小于当前根
                // 则该树也不是合法二叉树
                result[0] = 0;
            } else {
                // 说明该树是合法二叉树
                result[0] = 1;
                result[1] = left[1]; // 当前树的最小值是左子树的最小值
                result[2] = right[2]; // 当前树的最大值是右子树的最大值
            }
        } // 判断是否一个节点为空结束

        return result;        
    }

    bool isValidBST(TreeNode* root) {
        // 空指针不递归
        if (root == nullptr) return true;

        vector<int> result = PostTraversal(root);
        if (result[0] == 1) return true;
        else return false;
    }
};

思路2：二叉搜索树是有序的，采用中序遍历一定会产生一个有序序列。因此可以中序遍历生成数组，判断数组是否为递增的。

中序遍历这里选择采用迭代法实现。

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
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode *> st;
        // 空结点不入队
        if (root) st.push(root);
        vector<int> result; // 使用一个数组保存中序遍历结果
        while (!st.empty()) {
            // 取出当前节点
            TreeNode *cur = st.top();
            st.pop();

            if (cur) {
                // 如果不是空结点则尝试将右孩子入队
                if (cur->right) st.push(cur->right);

                // 将中间节点入队并使用一个空指针标记
                st.push(cur);
                st.push(nullptr);

                // 尝试将左孩子入队
                if (cur->left) st.push(cur->left);
            } else {
                // 如果是空结点说明下一个元素是应该处理的元素
                result.push_back(st.top()->val);
                st.pop();
            }
        }
        // 判断中序遍历的结果是否是递增的
        for (int i = 1; i < result.size(); i++) {
            if (result[i - 1] >= result[i]) return false;
        }
        return true;
    }
};

思路3：采用递归实现中序遍历，需要使用一个全局变量记录上一次的值。

1.递归的参数和返回值：参数是当前根节点，以及一个全局变量记录上一次的值；返回值是bool

2.递归的终止条件：空结点递归，表示true

3.递归的逻辑：首先递归左孩子，在递归过程中会更新左孩子的最后一个值；然后将全局变量与当前根节点进行比较；最后递归右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    long last_val = LONG_MIN;

    bool isValidBST(TreeNode* root) {
        // 递归终止条件
        if (!root) return true;

        // 首先递归左孩子
        if (!isValidBST(root->left)) return false;

        // 接着将上一次记录值与当前值比较
        if (last_val >= root->val) return false;
        last_val = root->val;

        // 最后递归右孩子
        if (!isValidBST(root->right)) return false;

        return true;
    }
};

思路4：采用迭代法实现思路3.实际上就是在中序遍历过程中完成比较。

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
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode *> st;
        // 空节点不入栈
        if (root) st.push(root);
        long int last_val = LONG_MIN;
        while (!st.empty()) {
            // 取出当前节点
            TreeNode *cur = st.top();
            st.pop();
            if (cur) {
                // 尝试将右孩子入栈
                if (cur->right) st.push(cur->right);

                // 将中间节点入栈
                st.push(cur);
                st.push(nullptr);

                // 尝试将左孩子入栈
                if (cur->left) st.push(cur->left);
            } else {
                // 处理栈顶元素
                cur = st.top();
                st.pop();

                if (last_val >= cur->val) return false;
                else last_val = cur->val;
            }
        }

        return true;
    }
};

二叉搜索树的最小绝对差

题目：530

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

思路1：二叉搜索树当作一个有序数组，本题就是求有序数组中的最小差值，因此一定是两个相邻节点的某个差值。

采用中序遍历，递归法，采用一个全局变量记录上一次的值，以及另一个全局变量记录最小绝对差

1.递归的参数和返回值：参数是当前子树根节点；无返回值

2.终止条件：遇到空结点直接返回

3.递归的逻辑：首先递归左孩子，然后计算上一个值与当前根节点值的绝对差，与最小绝对差进行比较；最后递归右孩子。

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 last_val = INT_MAX;
    int result = 0;

    void InorderTraversal(TreeNode *cur) {
        // 递归终止条件
        if (cur == nullptr) return;

        // 递归左孩子
        InorderTraversal(cur->left);

        // 处理当前根节点
        int tmp = abs(cur->val - last_val);
        last_val = cur->val;
        if (tmp <= result) result = tmp;

        // 递归右孩子
        InorderTraversal(cur->right);
    }

    int getMinimumDifference(TreeNode* root) {
        last_val = INT_MAX; // 上一次的值为最大值，保证
        result = INT_MAX; // 

        InorderTraversal(root);

        return result;
    }
};

上面的算法设计的不够优秀，因为上一次记录的值设置为INT_MAX，如果测试用例中也有这个值，那么会收到影响。

当初始值不好赋值时，可以使用指针，将指针初始化为空，当空指针时就知道这是第一次操作。

因此修改为：

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
class Solution {
public:
    TreeNode *last_node;
    int result;

    void InorderTraversal(TreeNode *cur) {
        // 递归终止条件
        if (cur == nullptr) return;

        // 递归左孩子
        InorderTraversal(cur->left);

        // 处理当前根节点
        if (last_node) {
            // 当上一个节点不是空结点时
            int tmp = abs(cur->val - last_node->val);
            if (tmp <= result) result = tmp;
        } 
        
        last_node = cur;

        // 递归右孩子
        InorderTraversal(cur->right);
    }

    int getMinimumDifference(TreeNode* root) {
        last_node = nullptr; // 上一次的值为最大值，保证
        result = INT_MAX; // 

        InorderTraversal(root);

        return result;
    }
};

思路2：迭代法，中序遍历的迭代法，同样使用两个全局变量记录上一个节点和最小绝对差。

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
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode *> st;
        // 空节点不入栈
        if (root) st.push(root);
        TreeNode *last_node = nullptr;
        int result = INT_MAX;

        while (!st.empty()) {
            // 取出当前节点
            TreeNode *cur = st.top();
            st.pop();
            if (cur) {
                // 如果非空则遍历
                if (cur->right) st.push(cur->right);

                st.push(cur);
                st.push(nullptr);

                if (cur->left) st.push(cur->left);
            } else {
                cur = st.top();
                st.pop();

                if (last_node) {
                    int tmp = abs(cur->val - last_node->val);
                    result = (result > tmp) ? tmp : result;
                }
                last_node = cur;
            }
        }

        return result;
    }
};

二叉搜索树中的众数

题目：501

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

分析：

二叉搜索树中的众数一定是连续的。所以这里可以使用一个全局变量记录所有众数，一个全局变量记录最大频率，一个全局记录当前出现频率，一个全局变量记录上一次的节点。

思路1：递归法，

1.递归的参数和返回值：参数是当前根节点和全局变量；无返回值

2.递归的终止条件：遇到空结点直接返回

3.递归的逻辑：首先递归左孩子；
然后处理中间节点：如果上一个结点为空指针，说明这是第一次，应该把count置为1；如果当前根节点的值不等于上一个节点的值，则更新当前频率为1
然后更新pre_node为当前根节点
最后根据次数更新结果数组：如果count==max_count则需要把当前值加进去；如果大于则之前的结果数组里面的值都作废，只添加当前值，并更新最大频率；如果小于什么都不做。
最后递归右孩子。

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
class Solution {
public:
    vector<int> result;
    int max_count;
    int count;
    TreeNode *last_node;

    void InorderTraversal(TreeNode *cur) {
        // 终止条件
        if (cur == nullptr) return;

        // 递归左孩子
        InorderTraversal(cur->left);

        // 处理中间节点的逻辑
        if (last_node != nullptr) {
            if (last_node->val == cur->val) count++;
            else count = 1;
        } else {
            count = 1;
        }
        last_node = cur;
        // 根据当前次数更新结果数组
        if (count == max_count) {
            result.push_back(cur->val);
        } else if (count > max_count) {
            result = vector<int>{cur->val};
            max_count = count;
        }

        // 递归右孩子
        InorderTraversal(cur->right);
    }

    vector<int> findMode(TreeNode* root) {
        // 初始化
        max_count = count = 0;
        last_node = nullptr;

        InorderTraversal(root);

        return result;
    }
};

思路2：采用迭代法。逻辑一样。

二叉树的最近公共祖先（递归需不需要返回值）

题目：236.

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

236

示例1：

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例2：

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

分析：

后序遍历就是天然的回溯。先遍历左右孩子，递归的返回值就是距离目标节点最近的子树根节点，如果左右孩子的返回结果都不为空，说明两个目标节点分布在两个孩子子树中，此时最近的公共祖先应该是当前根节点；如果其中一个返回结果为空，说明其中一个目标节点不在这颗子树中，但是另一个目标节点在其中一颗子树中，此时应该返回这颗子树；如果都为空，说明在当前根节点的左右子树中均没有目标节点，应该返回空。

1.递归的参数和返回值：参数是当前根节点和两个目标节点；返回值是节点指针

2.递归的终止条件：遇到空结点直接返回空，如果当前根节点就是其中一个目标节点则返回当前根节点；

3.递归的逻辑：与上面分析的一致。

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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root;

        // 先递归左右孩子
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);

        // 根据左右子树返回的结果判断
        if (left && right) {
            // 说明在目标节点分布在左右子树中
            // 此时最近的公共祖先就是当前根
            return root;
        } else if (!left && right) {
            // 说明其中一个节点分布在右子树中
            // 返回右子树，意义是返回非空节点说明当前根子树内存在一个目标
            return right;
        } else if (left && !right) {
            return left;
        } else {
            // 两颗子树均为空
            // 说明当前根子树不存在目标节点
            return nullptr;
        }
    }
};

我的思路：从上到下遍历每个结点，判断当前结点是否为两个目标节点的祖先（即分别判断两个目标结点是否在以当前节点为根节点的子树中），如果是祖先，那么就根据深度判断是否更新最近祖先。

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
class Solution {
public:
    int last_depth;
    TreeNode *last_grandp;
    TreeNode *p;
    TreeNode *q;

    // 寻找当前子树中是否出现目标结点
    bool findChildren(TreeNode *cur, TreeNode *target) {
        if (cur == nullptr) return false;

        if (cur == target) return true;

        if (findChildren(cur->left, target)) return true;
        if (findChildren(cur->right, target)) return true;
        
        return false;
    }

    // 采用递归法遍历
    void treaversal(TreeNode *cur, int depth) {
        if (cur == nullptr) return;

        // 首选处理当前根节点
        bool left_flag = findChildren(cur, p);
        bool right_flag = findChildren(cur, q);
        if (left_flag && right_flag) {
            if (last_grandp == nullptr) {
                last_depth = depth;
                last_grandp = cur;
            } else {
                if (depth > last_depth) {
                    last_grandp = cur;
                    last_depth = depth;
                }
            } // end if last_grandp is nullptr
        } // end if flags are true

        // 如果当前结点就是其中一个结点，那么不用再向下遍历
        if (cur == p || cur == q) return;
        // 遍历左子树
        treaversal(cur->left, depth + 1);
        // 遍历右子树
        treaversal(cur->right, depth + 1);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 初始化
        last_depth = 0;
        last_grandp = nullptr;
        this->p = p;
        this->q = q;

        treaversal(root, 1);

        return last_grandp;
    }
};

收获：判断递归需不需要返回值的逻辑：

如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？

搜索一条边的写法：

1
2
3
if (递归函数(root->left)) return ;

if (递归函数(root->right)) return ;

搜索整个树写法：

1
2
3
left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中

在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。

阶段总结4

合并两个二叉树：同时遍历和操作两个树

搜索二叉树：利用搜索二叉树的有序性，利用中序遍历将搜索二叉树看作是一个有序数组

判断一个二叉树是否为搜索二叉树：即判断一个二叉树在中序遍历下是否满足递增顺序

二叉搜索树的最小绝对差：也是利用二叉搜索树的有序性，需要注意的是初始化不好赋值时可以利用指针，因为空指针可以作为一个标志来使用

二叉搜索树中的众数：二叉搜索树中的众数一定是连续的

求二叉树的公共祖先：利用回溯（后序遍历）的方法从底向上遍历

二叉搜索树的最近公共祖先

题目：235

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

235

示例1：

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

分析：

这一题与上一题的区别就是公共祖先一定是在二者之间。

也就是说如果当前根节点的值位于p与q之间，说明刚好就是公共祖先。是否为最近公共祖先？如果向左子树继续搜索，那么一定不是q（假设为区间右边界）的祖先，同理对于右子树。所以一定是最近的公共祖先。

递归实现：

1.递归的参数：当前根节点和两个目标节点；返回值是结果节点

2.递归的终止：遇到当前根节点是空则返回空；如果当前根节点是其中一个，则返回空（题目中提到所有节点的值是唯一的）

3.递归的逻辑：判断当前根节点的值是否位于二者之间，如果位于二者之间则返回当前节点；如果当前根节点大于左边界，则向左孩子递归；否则向右孩子递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return root;
        
        // 判断当前根节点的值是否在之间
        if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } 
        if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        }

        return root;
    }
};

思路2：迭代法，逻辑与上面类似。

二叉搜索树的插入

题目：701

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

思路1：递归处理

1.递归的参数：当前根节点，需要插入的结点的值 递归的返回值：无
2.递归的终止条件：隐含在逻辑中，空结点不递归
3.递归逻辑：首先根据当前根节点的值判断应该插入左子树还是右子树；如果在左子树，先判断当前是有左孩子，如果没有左孩子就把这个值当作左孩子（这也就是终止体条件），如果有左孩子那么继续向左孩子递归；如果在右子树也是一样的处理。

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:
    void Traversal(TreeNode *cur, int val) {
        // 空结点不递归

        // 先根据当前根节点判断应该插在左子树还是右子树
        if (val < cur->val) {
            // 应该插在左子树
            // 先判断是否存在左子树
            if (cur->left == nullptr) {
                // 不存在左子树就把这个值当作左孩子
                cur->left = new TreeNode(val);
            } else {
                // 存在左子树就递归
                Traversal(cur->left, val);
            }
        } else {
            // 应该插在右子树
            if (cur->right == nullptr) cur->right = new TreeNode(val);
            else Traversal(cur->right, val); 
        }
    }

    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // 空指针不递归
        if (root == nullptr) return new TreeNode(val);

        Traversal(root, val);

        return root;
    }
};

思路2：迭代实现

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
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode *cur = root; // 遍历指针
        // 空指针不进入迭代
        if (cur == nullptr) return new TreeNode(val);

        // 由于是二叉搜索树
        // 一定能找到插入点
        while (true) {
            // 根绝当前节点的值判断插入左子树还是右子树
            if (val < cur->val) {
                // 插入左子树
                if (cur->left == nullptr) {
                    cur->left = new TreeNode(val);
                    return root;
                } else {
                    cur = cur->left;
                }
            } else {
                // 插入右子树
                if (cur->right == nullptr) {
                    cur->right = new TreeNode(val);
                    return root;
                } else {
                    cur = cur->right;
                }
            }
        } // 死循环

        exit(1);
    }
};

二叉搜索树的删除

题目：450

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

分析：找到相应的节点，同时需要一个全局变量记录指向这个节点的指针，方便后面修改指针的指向。找到节点之后，分以下情况：

（1）该节点是叶子节点：则直接删除即可，令指向该节点的指针指向空即可；

（2）该节点只有左孩子或者只有右孩子，令指向该节点的指针指向左孩子或者右孩子即可；

（3）该节点同时存在左孩子和右孩子：由于是二叉搜索树，左孩子的全部节点值一定小于右孩子，所以先找到右孩子的最左节点，令其左孩子等于当前节点的左子树，接着令指向当前节点的指针指向右子树即可。

PS：由于涉及到插入或者删除操作，为了防止插入和删除出现在根节点，因此可以创建一个虚拟根节点

思路1：递归实现，

1.递归的参数和返回值：参数是当前根节点和目标值；无返回值

2.递归的终止条件：遇到空结点直接返回

3.递归的逻辑：首先判断当前根是否为目标值，如果不是就分别递归左孩子和右孩子；如果是，就按照上面的分析处理。

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
class Solution {
public:
    TreeNode **prev; // 指向前一个节点的left或者right的指针
    void Traversal(TreeNode *cur, int key) {
        // 如果是空指针直接返回
        if (cur == nullptr) return;

        // 判断当前节点是否为目标值
        if (key < cur->val) {
            prev = &cur->left; // 更新指向前一个节点的left或right的指针
            Traversal(cur->left, key); // 向左孩子递归
        } else if (cur->val < key) {
            prev = &cur->right;
            Traversal(cur->right, key); // 向右孩子递归
        } else {
            // 当前节点就是目标值的节点
            if (cur->left == nullptr && cur->right == nullptr) {
                // 如果当前节点是一个叶子节点
                *prev = nullptr;
                delete cur;
            } else if (cur->left != nullptr && cur->right == nullptr) {
                // 如果只存在左孩子
                *prev = cur->left;
                delete cur;
            } else if (cur->left == nullptr && cur->right != nullptr) {
                // 如果只存在右孩子
                *prev = cur->right;
                delete cur;
            } else {
                // 如果同时存在左右孩子
                // 首先找到右子树的最左孩子节点
                TreeNode *target = cur->right;
                while (target->left) target = target->left;
                // 令左子树作为该节点的左孩子
                target->left = cur->left;

                // 令前一个节点的孩子为当前节点的右子树
                *prev = cur->right;

                delete cur;
            } // end wether cur
        } // end val

    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        // 创建虚拟头节点
        TreeNode *v_root = new TreeNode;
        v_root->left = root;
        prev = &v_root->left;

        Traversal(root, key);

        // 删除虚拟头节点
        TreeNode *tmp = v_root;
        v_root = v_root->left;
        delete tmp;

        return v_root;
    }
};

思路2：迭代法

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
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // 创建虚拟根节点，使得对于根和其它节点的处理一致
        TreeNode *v_root = new TreeNode;
        v_root->left = root;
        TreeNode **prev = &v_root->left; // 指向前一个节点的left或right的指针
        TreeNode *cur = root; // 遍历指针

        // 如果遇到空指针说明没有找到
        while (cur) {
            // 首先判断当前节点是否为目标节点
            if (cur->val < key) {
                prev = &cur->right;
                cur = cur->right;
            } else if (key < cur->val) {
                prev = &cur->left;
                cur = cur->left;
            } else {
                if (!cur->left && !cur->right) {
                    *prev = nullptr;
                    delete cur;
                } else if (cur->left && !cur->right) {
                    *prev = cur->left;
                    delete cur;
                } else if (!cur->left && cur->right) {
                    *prev = cur->right;
                    delete cur;
                } else {
                    // 先找到右子树的最左节点
                    TreeNode *target = cur->right;
                    while (target->left) target = target->left;
                    // 令最左节点的左孩子是左子树
                    target->left = cur->left;

                    *prev = cur->right;

                    delete cur;
                } // end if 判断当前节点孩子结束
                cur = nullptr;
            } // end if 判断当前节点的值是否符合要求结束
        } // end while 

        // 删除虚拟根节点
        TreeNode *tmp = v_root;
        v_root = v_root->left;
        delete tmp;

        return v_root;
    }
};

收获：普通二叉树（非二叉搜索树）的删除方式：代码中目标节点（要删除的节点）被操作了两次：

  • 第一次是和目标节点的右子树最左面节点交换。

  • 第二次直接被NULL覆盖了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if (root == nullptr) return root;
            if (root->val == key) {
                if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                    return root->left;
                }
                TreeNode *cur = root->right;
                while (cur->left) {
                    cur = cur->left;
                }
                swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
            }
            root->left = deleteNode(root->left, key);
            root->right = deleteNode(root->right, key);
            return root;
        }
    };

    这个代码是简短一些，思路也巧妙，但是不太好想，实操性不强

    二叉搜索树的修剪

    题目：669

    给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

    所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

    分析：

    如果当前根节点在区间左边，那么当前根节点和左子树整体可以删除，接着裁剪右子树；

    如果当前根节点在区间右边，那么当前根节点和右子树整体可以删除，接着裁剪左子树；

    如果当前根节点在区间内部，那么需要裁剪左子树和右子树。

    思路1：递归

    1.递归的参数和返回值：参数是当前根节点和区间；返回值是裁剪完成之后的树；

    2.递归的终止条件：如果当前结点是空结点则返回空；

    3.递归的逻辑：如果当前节点在区间左边，返回递归裁剪的右子树；如果在右边，返回递归裁剪的左子树；如果在内部，令左子树等于递归返回的左子树，令右子树等于递归返回的右子树。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        TreeNode* trimBST(TreeNode* root, int low, int high) {
            // 递归终止条件
            if (root == nullptr) return root;

            if (root->val < low) {
                return trimBST(root->right, low, high);
            } else if (root->val > high) {
                return trimBST(root->left, low, high);
            } else {
                root->left = trimBST(root->left, low, high);
                root->right = trimBST(root->right, low, high);
                return root;
            }
        }
    };

    思路2：迭代法

    因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。

    在剪枝的时候，可以分为三步：

    • 将root移动到[L, R] 范围内，注意是左闭右闭区间
    • 剪枝左子树
    • 剪枝右子树

    第一步是找到一个节点在范围里面（以这个根节点作为最终的根节点）
    第二步是修剪左子树：将根节点的左孩子值小于low的节点都删除，删除的过程就是令左孩子等于左孩子的右子树；然后再遍历根节点的左孩子，保证其左孩子也满足要求。

    第三步是修剪右子树。

    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
    class Solution {
    public:
        // 使用迭代
        TreeNode* trimBST(TreeNode* root, int low, int high) {
            if (root == nullptr) return nullptr;

            // 将头结点移动到[L, R]范围内
            while (root && (root->val < low || root->val > high)) {
                if (root->val < low) root = root->right;
                else root = root->left;
            }

            TreeNode *cur = root;
            // 将根节点的左孩子都小于low节结点删除
            while (cur) {
                while (cur->left && cur->left->val < low) {
                    cur->left = cur->left->right;
                }

                cur = cur->left;
            }

            cur = root;
            while (cur) {
                while (cur->right && cur->right->val > high) {
                    cur->right = cur->right->left;
                }

                cur = cur->right;
            }

            return root;
        }
    };

将有序数组换转为二叉搜索树

题目：108

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

分析：平衡二叉树指的是所有节点的左右子树的高度差绝对值最多为1.通俗理解就是是的每一个节点的左右子树节点数目大致相同。

可以将数组均分成两组，然后以中间节点作为根，以左边一组构建左子树，以右边一组构建右子树。

思路1：递归

1.递归的参数和返回值：参数是数组，以及构建的范围[start, end)；返回值是构建完成的子树

2.递归的终止条件：当左右边界相等时返回空

3.递归的逻辑：取范围内的中点mid = start + (end - start) / 2作为根节点，使用范围[start, mid)构建左子树；使用范围[mid + 1, end)构建右子树

如果数组长度为偶数，中间节点有两个，取哪一个？取哪一个都可以，只不过构成了不同的平衡二叉搜索树。
例如：输入：[-10,-3,0,5,9]，如下两棵树，都是这个数组的平衡二叉搜索树：

108.将有序数组转换为二叉搜索树 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode *Build(vector<int> &nums, int start, int end) {
        // 递归终止条件
        if (start == end) return nullptr;

        // 取中间下标对应的值构建根
        int mid = start + (end - start) / 2;
        TreeNode *root = new TreeNode(nums[mid]);
        // 构建左子树和右子树
        root->left = Build(nums, start, mid);
        root->right = Build(nums, mid + 1, end);

        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // 空列表也能构建
        return Build(nums, 0, nums.size());
    }
};

思路2：迭代法

迭代法就是使用数据结构模拟递归过程。这里使用一个队列保存遍历的节点，一个队列存放左区间下标，一个队列存放右区间下标。

在每次循环中，首先取出当前待处理节点，令节点的值等于中间下标的值，然后处理左区间：如果左区间存在，那么创建左孩子节点，令当前节点的左孩子等于这个节点，并令左孩子入队，以及左孩子对应的范围入队。右区间同理。

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
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // 下面的代码要求至少有一个元素
        if (nums.size() == 0) return nullptr;
        
        queue<TreeNode *> node_que;
        queue<int> left_que;
        queue<int> right_que;
        // 创建根节点入队
        TreeNode *root = new TreeNode;
        node_que.push(root);
        left_que.push(0);
        right_que.push(nums.size());

        // 每次迭代处理一个元素
        while (!node_que.empty()) {
            // 取出当前根节点
            TreeNode *cur = node_que.front();
            node_que.pop();
            int left = left_que.front();
            left_que.pop();
            int right = right_que.front();
            right_que.pop();

            // 计算中间下标
            int mid = left + (right - left) / 2;
            cur->val = nums[mid];

            // 处理左区间
            if (left < mid) {
                // 创建一个左孩子节点
                // 并将左孩子的范围入队
                cur->left = new TreeNode;
                node_que.push(cur->left);
                left_que.push(left);
                right_que.push(mid);
            }
            // 处理右区间
            if (right > mid + 1) {
                cur->right = new TreeNode;
                node_que.push(cur->right);
                left_que.push(mid + 1);
                right_que.push(right);
            }
        }

        return root;
    }
};

这里使用迭代模仿递归时，虽然递归是在每一层中创建新节点，但是在迭代中不能在每一层创建新节点。这是因为如果在该层创建节点，就无法记录该层的左右孩子指针的指向（这个指向需要轮到孩子时处理）。所以在迭代中每一层创建孩子节点，令保存的父亲节点的左右孩子指向他们。

二叉搜索树转换为累加树

题目：538

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

分析：

思路1：可以先使用中序遍历记录所有二叉树的值，然后从后向前累积和，最后再次遍历二叉搜索树重新赋值。

关键在于如何对二叉搜索树进行中序遍历的逆序遍历。

思路2：递归法

1.递归的参数和返回值：参数是当前根节点；无返回值，但是使用一个全局变量记录累积和

2.递归的终止条件：当遇到空结点返回；

3.递归的逻辑：先递归右孩子；更新当前根的值为 val + 累积和；递归左孩子

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:
    int sum;

    void Traversal(TreeNode *cur) {
        // 递归终止条件
        if (cur == nullptr) return;

        // 递归右孩子
        Traversal(cur->right);
        // 更新当前节点的值
        cur->val += sum;
        // 更新sum
        sum = cur->val;
        // 递归左孩子
        Traversal(cur->left);
    }

    TreeNode* convertBST(TreeNode* root) {
        // 初始化
        sum = 0;
        
        // 空结点可以进行递归
        Traversal(root);

        return root;
    }
};

思路3：迭代法

使用栈模拟中序遍历的逆序

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
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        stack<TreeNode *> st;
        // 空节点不入栈
        if (root) st.push(root);
        int sum = 0; // 累积和

        while (!st.empty()) {
            // 取出当前节点
            TreeNode *cur = st.top();
            st.pop();
            
            if (cur) {
                // 非空则遍历
                if (cur->left) st.push(cur->left);

                // 标记当前节点
                st.push(cur);
                st.push(nullptr);

                if (cur->right) st.push(cur->right);
            } else {
                // 处理栈顶节点
                cur = st.top();
                st.pop();

                // 更新栈顶节点的值
                cur->val += sum;
                sum = cur->val;
            }
        }

        return root;
    }
};

实际上sum就是上一个节点的值，所以使用一个指针记录上一个节点也可以。

阶段总结5

二叉搜索树的最近公共祖先：根据二叉树的性质，如果一个节点在p、q节点的范围内，那么该节点一定是一个祖先。是否为最近的公共祖先呢？一定是的，假设再向左子树寻找，这个左子树一定不是右边界的祖先，因为左子树的值 < 根 < 右子树的q。

二叉搜索树的插入：与每一个节点进行比较，确定应该插在左子树还是右子树；然后如果插入点是空则可以直接插入，否则就需要继续与这个非空子树的根进行比较。

二叉搜索树的删除：找到删除点之后，分情况讨论：（1）当前节点是叶子节点，可以直接删除；（2）当前节点某一个孩子不是空，那么需要令当前节点的父节点指向这个非空孩子（所以就需要记录前一个节点的信息）；（3）如果左右孩子都不为空，由于是二叉搜索树，所以将做左子树插到右子树上，再令父节点指向这个右子树

将有序数组换转为二叉搜索树：均分成两段进行构建。如果是偶数有两种根的选择，构建的树不一样。

二叉搜索树转换为累加树：二叉树的逆中序遍历。

二叉树总结

  • 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
  • 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
  • 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

注意在普通二叉树的属性中，我用的是一般为后序，例如单纯求深度就用前序，二叉树：找所有路径 (opens new window)也用了前序，这是为了方便让父节点指向子节点。

所以求普通二叉树的属性还是要具体问题具体分析。

我的总结就是，对于二叉树，最重要的是基本遍历方法（分为递归和迭代法），所有对于二叉树的处理都是在遍历的基础上实现的。即遍历顺序和处理顺序是息息相关的。

另外就是要注意二叉树的一些性质，利用性质解决问题。