【LeetCode】-二叉树_leetcode 二叉树

前言

初识LeetCode与算法，将在此系列文章里面，记录自己的算法学习经历，前期主要是监督自己学习打卡，后期我会将自己对知识的理解，慢慢补充到文章当中，希望大家能在阅读我的文章中，有所收获。该系列文章的刷题顺序以代码随想录为线索。

一、二叉树的层序遍历

题目：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、画一个二叉树，结合代码，就能将代码更好的理解！

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue <TreeNode*> 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++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            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

二、 翻转二叉树

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

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：

代码：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return root;
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;

    }
};
1
2
3
4
5
6
7
8
9
10
11

三、 对称二叉树

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

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        if(left == NULL && right != NULL) return false;
        else if(left != NULL && right == NULL) return false;
        else if(left == NULL && right == NULL) return true;
        else if(left -> val != right -> val) return false;

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool isSame = outside && inside;
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return compare(root->left, root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、 二叉树的最大深度

题目：
给定一个二叉树，找出其最大深度。

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

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

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3
1

/
9 20
/
15 7

返回它的最大深度 3 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    int getDepth(TreeNode* node){
        if(node == NULL) return 0;
        int leftdepth = getDepth(node->left);
        int rightdepth = getDepth(node->right);
        int depth = 1 + max(leftdepth,rightdepth);
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

五、 二叉树的最小深度

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    int getDepth(TreeNode* node){
        if(node == NULL) return 0;
        int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);
        if(node->left == NULL && node->right != NULL){
            return 1 + rightDepth;
        }
        if(node->left != NULL && node->right == NULL){
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

六、 二叉树的最小深度

题目：
给出一个完全二叉树，求出该树的节点个数。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6
1
2

示例 2：

输入：root = []
输出：0
1
2

示例 3：

输入：root = [1]
输出：1
1
2

提示：

树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树
1
2
3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    int getDepth(TreeNode* node){
        if(node == NULL) return 0;
        int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);
        if(node->left == NULL && node->right != NULL){
            return 1 + rightDepth;
        }
        if(node->left != NULL && node->right == NULL){
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

七、 平衡二叉树

题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
1

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    int getNodesNum(TreeNode* cur){
        if(cur == NULL) return 0;
        int leftNum = getNodesNum(cur->left);
        int rightNum = getNodesNum(cur->right);
        int treeNum = leftNum + rightNum + 1;
        return treeNum;
    }
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

八、二叉树的层序遍历

题目：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来，一是确定参数和返回值；二是确定终止条件；三是确定单层循环的内容

代码：

class Solution {
public:
    int getHeight(TreeNode* node){
        if(node == NULL){
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if(leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if(rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight,rightHeight);

    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

九、二叉树的所有路径

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

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

示例 1：

输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]

示例 2：

输入：root = [1]
输出：[“1”]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来，一是确定参数和返回值；二是确定终止条件；三是确定单层循环的内容

代码：

class Solution {
private:
    void traversal(TreeNode* node, vector<int>& path, vector<string>& result){
        path.push_back(node->val);
        if(node->left == NULL && node->right == NULL){
            string sPath;
            for(int i = 0; i < path.size() - 1; i++){
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size()-1]);
            result.push_back(sPath);
            return;
        }
        if(node->left){
            traversal(node->left, path, result);
            path.pop_back();
        }
        if(node->right){
            traversal(node->right, path, result);
            path.pop_back();
        }
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(root == NULL) return result;
        traversal(root, path, 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

十、左叶子之和

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

示例 1：

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);
        int rightValue = sumOfLeftLeaves(root->right);

        int midValue = 0;

        if(root->left && !root->left->left && !root->left->right){
            midValue = root->left->val;
        }

        int sum = midValue + leftValue + rightValue;
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

十一、找树左下角的值

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

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

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

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

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1 
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    int maxLen = INT_MIN;
    int maxleftValue;
    void traversal(TreeNode* root, int leftLen){
        if(root->left == NULL && root->right == NULL){
            if(leftLen > maxLen){
                maxLen = leftLen;
                maxleftValue = root->val;
            }
            return;
        }
        if(root->left){
            leftLen++;
            traversal(root->left,leftLen);
            leftLen--;
        }
        if(root->right){
            leftLen++;
            traversal(root->right,leftLen);
            leftLen--;
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return maxleftValue;
    }
};
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

十二、路径总和

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

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
1
2
3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    bool traversal(TreeNode* cur, int count){
        if(!cur->left && !cur->right && count == 0) return true;
        if(!cur->left && !cur->right) return false;

        if(cur->left){
            count -= cur->left->val;
            if (traversal(cur->left, count)) return true;
            count +=cur->left->val;
        }

        if(cur->right){
            count -= cur->right->val;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val;
        }
        return false;
    }
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) return false;
        return traversal(root, targetSum - root->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

十三、路径总和 II

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

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
1
2
3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void traversal(TreeNode* cur, int count){
        if(!cur->left && !cur->right && count == 0){
            result.push_back(path);
            return;
        }
        if(!cur->left && !cur->right) return;
        if(cur->left){
            path.push_back(cur->left->val);
            count -= cur->left->val;
            traversal(cur->left, count);
            count += cur->left->val;
            path.pop_back();
        }
         if(cur->right){
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traversal(cur->right, count);
            count += cur->right->val;
            path.pop_back();
        }
        return;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        result.clear();
        path.clear();
        if(root == NULL) return result;
        path.push_back(root->val);
        traversal(root, targetSum - root->val);
        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

十四、最大二叉树

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

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

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

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：

• [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
  • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
    • 空数组，无子节点。
    • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
      • 空数组，无子节点。
      • 只有一个元素，所以子节点是一个值为 1 的节点。
  • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
    • 只有一个元素，所以子节点是一个值为 0 的节点。
    • 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同
1
2
3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    TreeNode* travesal(vector<int>& nums, int left, int right) {
        if(left >= right) return nullptr;

        int maxValueIndex = left;
        for(int i = left+1; i < right; i++){
            if(nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        }
        TreeNode* root = new TreeNode(nums[maxValueIndex]);

        root->left = travesal(nums, left, maxValueIndex);
        root->right = travesal(nums, maxValueIndex + 1, right);
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums){
        return travesal(nums, 0, nums.size());
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

十五、合并二叉树

题目：
给你两棵二叉树： root1 和 root2 。

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

返回合并后的二叉树。

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

示例 1：

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

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL) return root2;
        if(root2 == NULL) return root1;

        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

十六、二叉搜索树中的搜索

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

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

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

Example 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107
1
2
3
4

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == NULL || root->val == val) return root;
        if(root->val > val) return searchBST(root->left, val);
        if(root->val < val) return searchBST(root->right, val);
        return NULL; 
    }
};
1
2
3
4
5
6
7
8
9

十七、验证二叉搜索树

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

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

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root){
        if(root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear();
        traversal(root);
        for(int i = 1; i < vec.size(); i++){
            if(vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

十八、二叉搜索树的最小绝对差

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

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

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
int result = INT_MAX;
TreeNode* pre;
void traversal(TreeNode* cur){
    if(cur == NULL) return;
    traversal(cur->left);
    if(pre != NULL){
        result = min(result, cur->val - pre->val);
    }
    pre = cur;
    traversal(cur->right);
}

public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

十九、二叉搜索树中的众数

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

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

假定 BST 满足如下定义：

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

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
void searchBST(TreeNode* cur, unordered_map<int,int>& map){
    if (cur == NULL) return;
    map[cur->val]++;
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return;
}
bool static cmp(const pair<int, int>& a, const pair<int, int>& b){
    return a.second > b.second;
}
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map;
        vector<int> result;
        if(root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(),cmp);
        result.push_back(vec[0].first);
        for(int i = 1; i < vec.size(); i++){
            if(vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        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

二十、二叉树的最近公共祖先

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
1
2
3
4
5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == q || root == p || root ==NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL) return root;
        if(left != NULL && right == NULL) return left;
        else if(left == NULL && right != NULL) return right;
        else{
            return NULL;
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

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

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

示例 1:

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

示例 2:

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

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
1
2

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q){
        if(cur == NULL) return cur;

        if(cur->val > p->val && cur->val > q->val){
            TreeNode* left = traversal(cur->left, p, q);
            if(left != NULL){
                return left;
            }
        }
        if(cur->val < p->val && cur->val < q->val){
            TreeNode* right = traversal(cur->right, p, q);
            if(right != NULL){
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root,p,q);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二十二、二叉搜索树中的插入操作

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

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

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

树中的节点数将在 [0, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是 独一无二 的。
-108 <= val <= 108
保证 val 在原始BST中不存在。
1
2
3
4
5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL){
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if(root->val > val) root->left = insertIntoBST(root->left, val);
        if(root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

二十三、删除二叉搜索树中的节点

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

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

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

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105
1
2
3
4
5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr) return root;
        if(root->val == key){
            if(root->left == nullptr && root->right == nullptr){
                delete root;
                return nullptr;
            }
            else if(root->left == nullptr){
                auto retNode = root->right;
                delete root;
                return retNode;
            }
            else if(root->right == nullptr){
                auto retNode = root->left;
                delete root;
                return retNode;
            }
            else{
                TreeNode* cur = root->right;
                while(cur->left != nullptr){
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* tmp = root;
                root = root->right;
                delete tmp;
                return root;
            }

        }
            if(root->val > key) root->left = deleteNode(root->left, key);
            if(root->val < key) root->right = deleteNode(root->right, key);
            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

二十四、修剪二叉搜索树

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

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

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是 唯一 的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104
1
2
3
4
5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr) return nullptr;
        if(root->val < low){
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }
        if(root->val > high){
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }

        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low,high);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列
1
2
3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private: 
    TreeNode* traversal(vector<int>& nums, int left, int right){
        if(left > right) return nullptr;
        int mid = left + ((right - left)/2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root =  traversal(nums, 0, nums.size()-1);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二十六、把二叉搜索树转换为累加树

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

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

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

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
1
2
3
4

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    int pre;
    void traversal(TreeNode* cur){
        if(cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二十七、把二叉搜索树转换为累加树

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

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

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

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
1
2
3
4

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、按照递归三步法来进行，第一步先确定参数和返回值；第二步确定终止条件；第三步确定单层循环的内容；

代码：

class Solution {
private:
    int pre;
    void traversal(TreeNode* cur){
        if(cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17