跳转至

二叉搜索树相关题目

约 4215 个字 753 行代码 22 张图片 预计阅读时间 23 分钟

本篇介绍

二叉搜索树是一种特殊的二叉树，其有下面的特性：

  1. 中序遍历的结果是升序
  2. 任意节点左子树的所有节点的值都比其根节点的值小
  3. 任意节点右子树的所有节点的值都比其根节点的值大

根据上面的特性，有些题目虽然可以使用通用的解法，但是如果是二叉搜索树就会有更简洁且高效的解法

力扣700.二叉搜索树中的搜索

力扣700.二叉搜索树中的搜索

问题描述：

Quote

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

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

示例 1:

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

示例 2:

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

思路分析：

本题的基本思路是根据二叉搜索树的特性进行折半查找，但是需要注意，本题虽然说返回的是以查找到的节点的子树，实际上还是返回指定的节点，只是在后台会用这个根节点遍历整棵子树，这一点是不需要刷题者关心的问题

参考代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution700
{
public:
    TreeNode *searchBST(TreeNode *root, int val)
    {
        if (!root)
            return nullptr;

        else if (root->left && val < root->val)
            return searchBST(root->left, val);
        else if (root->right && val > root->val)
            return searchBST(root->right, val);

        return root->val == val ? root : nullptr;
    }
};

力扣98.验证二叉搜索树

力扣98.验证二叉搜索树

问题描述：

Quote

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

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

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

示例 1：

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

示例 2：

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

思路分析：

  1. 解法1：中序遍历有序+额外空间

    本题最直接的思路就是根据题目给出的规则模拟，但是不能仅仅只判断单棵子树是否满足二叉搜索树的条件，例如下面的一棵树：

    Text Only
    1
2
3
          5
  4       6
       3     7

    这棵树根节点为5，其左子树是4，4<5，右子树为6，6>5，当前子树满足二叉搜索树的条件 再看根节点为6的子树，左子树为3，3<6，右子树为7，7>6，当前子树满足二叉搜索树的条件 但是二叉搜索树除了叫「搜索树」，还叫「排序树」，即其中序遍历的结果是一个升序排序 很明显，当前子树如果进行中序遍历，结果是45367，不满足排序树的特点，所以其不是二叉搜索树 通过上面的例子可以看成，仅仅只判断每一棵子树是否是二叉搜索树不一定保证本题可以通过 最简单的做法就是将二叉树的中序遍历结果插入到数组中，判断数组中的元素是否是升序，如果是那么当前树就是二叉搜索树，否则就不是

  2. 解法2：双指针

    使用一个节点记录前一个节点的数值，在遍历二叉树的过程中直接进行比较

  3. 解法3：双指针+剪枝

    双指针方案写法和上面的双指针一致，但是如果判断左子树节点不符合就可以直接返回而不再需要再去根节点和右子树，所以可以通过这一步减少一些判断过程，这个优化过程也被称为剪枝

参考代码：

C++
 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
class Solution98_1
{
public:
    void traversal(TreeNode* root, vector<int>& ret)
    {
        if(!root)
            return;

        traversal(root->left, ret);
        ret.push_back(root->val);
        traversal(root->right, ret);
    }

    bool isValidBST(TreeNode *root)
    {
        vector<int> ret;

        traversal(root, ret);

        for(int i = 0; i < ret.size() - 1; i++)
            if(ret[i] >= ret[i + 1])
                return false;

        return true;
    }
};
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution98_2
{
public:
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode *root)
    {
        if(!root)
            return true;

        bool left = isValidBST(root->left);
        if(pre && pre->val >= root->val)
            return false;

        // 更新pre为前一个节点
        pre = root;
        bool right = isValidBST(root->right);

        return left && right;
    }
};
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution98_3
{
public:
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode *root)
    {
        if(!root)
            return true;

        bool left = isValidBST(root->left);
        // 剪枝
        if(!left)
            return false;
        if(pre && pre->val >= root->val)
            return false;

        // 更新pre为前一个节点
        pre = root;
        bool right = isValidBST(root->right);

        return left && right;
    }
};

力扣530.二叉搜索树的最小绝对差

力扣530.二叉搜索树的最小绝对差

问题描述：

Quote

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

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

示例 1：

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

示例 2：

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

思路分析：

本题的基本思路是当前节点值减去前一个节点值，取minVal和该值的最小值即可

参考代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution530
{
public:
    int minVal = INT_MAX;
    TreeNode *prev = nullptr;

    int getMinimumDifference(TreeNode *root)
    {
        if (!root)
            return 0;

        getMinimumDifference(root->left);
        if (prev && prev->val != root->val)
            minVal = min(minVal, abs(root->val - prev->val));
        prev = root;
        getMinimumDifference(root->right);

        return minVal;
    }
};

力扣501.二叉搜索树中的众数

力扣501.二叉搜索树中的众数

问题描述：

Quote

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

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

假定BST满足如下定义：

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

示例 1：

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

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

思路分析：

  1. 解法1：中序遍历有序+个数统计

    本题最直观的思路就是遍历二叉搜索树，将元素依次插入vector，遍历vector使用哈希表统计元素出现的次数，找出出现次数最大的所有元素，这个思路适合于普通的二叉树，所以也同样适合于二叉搜索树

  2. 解法2：双指针

    根据二叉搜索树的特性可以保证相同的元素出现在一起，类比有序数组。注意下面示例代码里面的一些处理技巧

参考代码：

C++
 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 Solution501_1
{
public:
    void traversal(TreeNode *root, unordered_map<int, int> &countMap)
    {
        if (!root)
            return;

        traversal(root->left, countMap);
        // 统计出现频率
        countMap[root->val]++;
        traversal(root->right, countMap);
    }

    vector<int> findMode(TreeNode *root)
    {

        unordered_map<int, int> countMap;
        traversal(root, countMap);

        int maxCount = 0;
        vector<int> ret;
        for (auto &kv: countMap)
        {
            if (kv.second > maxCount)
                maxCount = kv.second;
        }

        for (auto &kv: countMap)
        {
            if (kv.second == maxCount)
                ret.push_back(kv.first);
        }

        for (auto &kv: countMap)
        {
            // 注意使用find确保当前插入的元素不存在于结果集中
            if (kv.second == maxCount && kv.first != ret[0] && find(ret.begin(), ret.end(), kv.first) == ret.end())
                ret.push_back(kv.first);
        }

        return ret;
    }
};
C++
 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
class Solution501_2
{
public:
    // 记录最大频率
    int maxCount = 0;
    // 记录当前元素出现的频率
    int count = 0;
    // 结果集
    vector<int> ret;
    // 上一个节点
    TreeNode *prev = nullptr;

    void traversal(TreeNode *root)
    {
        if (!root)
            return;

        // 中序遍历
        traversal(root->left);

        // 中间处理
        // 统计当前元素出现频率
        if (prev == nullptr) // 前一个为空元素，说明当前元素一定为新出现的元素，count更新为1
            count = 1;
        else if (prev->val == root->val) // 前一个元素和当前元素相等，说明一定是重复元素
            count++;
        else
            count = 1; // 前一个元素和当前元素不相等，说明遇到新元素，count更新为1
        // 更新prev
        prev = root;

        // 如果count与maxCount相等，说明此时找到了最大出现频率的元素
        // 更新结果集
        // 使用if确保只插入一次满足最大出现频率的元素
        if (count == maxCount)
            ret.push_back(root->val);

        // 如果count大于maxCount说明前面已经更新的结果集有误，此时更新maxCount和结果集
        // 通过第二次的更新一定可以满足在当前状态下结果集中是当前出现频率最大的
        // 如果下一次有不同的值但是出现频率与最大频率相同，那么会因为上面的if插入到结果集而不会更新结果集
        if (count > maxCount)
        {
            maxCount = count;
            // 清空上一次的结果集
            ret.clear();
            // 重新更新结果集
            ret.push_back(root->val);
        }

        traversal(root->right);
    }

    vector<int> findMode(TreeNode *root)
    {
        traversal(root);

        return ret;
    }
};

力扣235.二叉搜索树的最近公共祖先

力扣235.二叉搜索树的最近公共祖先

问题描述：

Quote

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

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

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

示例 1:

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

示例 2:

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

思路分析：

  1. 解法1：针对任何二叉树

    第一种写法和二叉树基础题目篇：力扣236的写法2一模一样，因为二叉搜索树本质也是二叉树

  2. 解法2：二叉搜索树

    第二种解法就略有不同，因为需要用到二叉搜索树的特性：左子树所有节点均小于根节点，右子树所有节点均大于根节点可以分出下面的三种情况：

    1. 当前节点大于p和q，说明最近公共祖先在左子树
    2. 当前节点小于p和q，说明最近公共祖先在右子树
    3. 当前节点介于p和q，说明当前节点就是最近公共祖先

    注意，不会出现「当前节点介于p和q，说明当前节点不是最近公共祖先」的情况，因为一旦当前节点介于p和q，则左子树一定小于当前节点，右子树一定大于当前节点，那么当前节点不论是向左遍历还是向右遍历都会出现错过一个节点的情况

参考代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution235_1
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (root == p || root == q || root == nullptr)
            return root;

        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);

        // 如果左孩子不为空，右孩子也不为空，说明当前函数栈帧的root的值就是最近公共祖先
        if (left && right)
            return root;
        else if (!left && right) // 如果左为空，右不为空，说明还没有找到最近公共祖先，只找到了一棵子树的根
            return right;
        else if (left && !right) // 同上面的情况
            return left;

        return nullptr;
    }
};
C++
 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 Solution235_2
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (!root)
            return root;

        // 如果当前节点的值在p值和q值之间，则说明一定是最进公共祖先，因为如果p和q不在同一个子树
        // 那么根据二叉搜索树定义就会出现：
        // 1. p和q都在当前节点左侧
        // 2. p和q都在当前节点右侧

        // 当前节点比p和q都大，走左子树继续找
        if (root->val > p->val && root->val > q->val)
        {
            TreeNode *left = lowestCommonAncestor(root->left, p, q);
            if (left)
                return left;
        }

        // 当前节点比p和q都小，走右子树继续找
        if (root->val < p->val && root->val < q->val)
        {
            TreeNode *right = lowestCommonAncestor(root->right, p, q);
            if (right)
                return right;
        }

        // 如果不满足上面三个if，说明当前节点就在p和q中间，即为最近公共祖先
        return root;
    }
};

力扣701.二叉搜索树中的插入操作

力扣701.二叉搜索树中的插入操作

问题描述：

Quote

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

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

示例 1：

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

解释：另一个满足题目要求可以通过的树是：

示例 2：

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

示例 3：

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

思路分析：

二叉搜索树的插入相对容易，只需要根据二叉搜索树的性质遍历二叉树找到合适的插入位置插入节点即可

参考代码：

C++
 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 Solution701
{
public:
    TreeNode *insertIntoBST(TreeNode *root, int val)
    {
        // 根节点为空，则当前节点作为根节点
        if (!root)
            return new TreeNode(val);

        TreeNode *cur = root;
        // 记录前一个节点
        TreeNode *prev = nullptr;
        while (cur)
        {
            // 当前节点的值小于val，走到右子树
            prev = cur;
            if (cur->val < val)
                cur = cur->right;
            else if (cur->val > val) // 当前节点的值小于val，走到左子树
                cur = cur->left;
        }

        if (val < prev->val)
            prev->left = new TreeNode(val);
        else if (val > prev->val)
            prev->right = new TreeNode(val);

        return root;
    }
};

力扣450.删除二叉搜索树中的节点

力扣450.删除二叉搜索树中的节点

问题描述：

Quote

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

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

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

示例 1:

C++
1
2
输入：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:

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

示例 3:

C++
1
2
输入: root = [], key = 0
输出: []

思路分析：

见数据结构：二叉搜索树篇

参考代码：

C++
  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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
class Solution450
{
public:
    // 判断查找的节点是否存在于BST中
    bool find(TreeNode *root, int key)
    {
        TreeNode *cur = root;
        while (cur)
        {
            // 当前节点偏大，走左子树
            if (cur->val > key)
                cur = cur->left;
            else if (cur->val < key) // 当前节点偏小，走右子树
                cur = cur->right;
            else
                return true; // 找到返回true
        }

        return false; // 循环走完说明没找到
    }
    TreeNode *deleteNode(TreeNode *root, int key)
    {
        // 根节点为空不执行或者不存在指定的key则返回空删除
        if (!root)
            return nullptr;

        if (!find(root, key))
            return root;

        // 先查找到指定节点
        TreeNode *cur = root;
        TreeNode *prev = prev;

        while (cur)
        {
            // 记录当前节点
            if (cur->val > key)
            {
                // 注意prev的位置要在if里面
                // 防止出现下一次cur为待删除的节点时，prev也变成了当前待删除的节点
                prev = cur;
                cur = cur->left;
            }
            else if (cur->val < key)
            {
                prev = cur;
                cur = cur->right;
            }
            else // 相等时执行删除
            {
                // 第一种和第二种情况
                // 如果当前节点的左孩子为空
                if (!cur->left)
                {
                    // 注意根节点为待删除的数值时需要单独考虑
                    if(cur == root)
                        root = cur->right;
                    else if (prev->left == cur) // 判断当前节点是其父亲节点的左孩子还是右孩子
                        prev->left = cur->right;
                    else if (prev->right == cur)
                        prev->right = cur->right;
                    delete cur;
                }
                else if (!cur->right)
                {
                    // 注意根节点为待删除的数值时需要单独考虑
                    if(cur == root)
                        root = cur->left;
                    else if (prev->left == cur)
                        prev->left = cur->left;
                    else if (prev->right == cur)
                        prev->right = cur->left;
                    delete cur;
                }
                else
                {
                    // 第三种情况
                    // 先找到待删除节点的右孩子的最左孩子
                    TreeNode *replaceNode = cur->right;
                    TreeNode *replaceNodePrev = cur;

                    while (replaceNode->left)
                    {
                        replaceNodePrev = replaceNode;
                        replaceNode = replaceNode->left;
                    }

                    // 将待删除节点的值替换为右孩子的最左孩子的值
                    cur->val = replaceNode->val;
                    if (replaceNode == replaceNodePrev->left)
                        replaceNodePrev->left = replaceNode->right;
                    else if (replaceNode == replaceNodePrev->right)
                        replaceNodePrev->right = replaceNode->right;

                    delete replaceNode;
                }
                break;
            }
        }

        return root;
    }
};

力扣669.修剪二叉搜索树

力扣669.修剪二叉搜索树

问题描述：

Quote

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

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

示例 1：

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

示例 2：

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

思路分析：

本题不可以使用二叉树删除节点的逻辑，因为题目提到了不能修改二叉树的父子关系，而在二叉树删除节点的过程中会涉及到挪动节点，从而导致父子关系改变。本题的正确做法是：直接删除指定节点，如果当前节点不在要求的[low, high]中，就找到其对应的子树继续遍历：

  1. 如果当前节点小于low，因为是二叉搜索树，所以其左子树的全部节点一定也小于low，此时只需要向右子树递归判断找到满足条件的子树返回
  2. 如果当前节点大于high，因为是二叉搜索树，所以其左子树的全部节点一定也大于high，此时只需要向左子树递归判断找到满足条件的子树返回

参考代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution669
{
public:
    TreeNode *trimBST(TreeNode *root, int low, int high)
    {
        // 如果节点为空，直接返回空
        if (!root)
            return nullptr;

        // 如果当前节点小于low，因为是二叉搜索树，所以其左子树的全部节点一定也小于low
        // 此时只需要向右子树递归判断找到满足条件的子树返回
        if (root->val < low)
            return trimBST(root->right, low, high); // 直接返回子树给当前节点的父亲节点相当于删除当前节点
        else if (root->val > high) // 否则向左遍历
            return trimBST(root->left, low, high);

        // 链接子树
        // 如果不满足上面的条件，说明当前节点在[low, high]之内，继续向下遍历
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        return root;
    }
};

力扣108.将有序数组转换为二叉搜索树

力扣108.将有序数组转换为二叉搜索树

问题描述：

Quote

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

示例 1：

C++
1
2
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]

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

示例 2：

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

思路分析：

本题不可以直接使用二叉搜索树的节点插入方法，因为这个方法没有考虑到平衡的情况从而导致二叉树变为单链表。因为本题的数组是升序排序的，所以默认情况下所有的节点也就是二叉搜索树的中序遍历结果

需要注意的是，本题已经提到了二叉搜索树最后的结构可以不同，所以可以直接取中间值作为根节点，这样就可以保证左右子树的高度最大不会超过1

参考代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution108
{
public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {
        if (nums.size() == 0)
            return nullptr;

        // 取出中间值作为根节点
        int mid = (nums.size() - 1) / 2;
        TreeNode *root = new TreeNode(nums[mid]);

        // 根据根节点位置构造左子树和右子树——左闭右开区间
        vector<int> left(nums.begin(), nums.begin() + mid);
        vector<int> right(nums.begin() + mid + 1, nums.end());

        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);

        return root;
    }
};

力扣538.把二叉搜索树转换为累加树

力扣538.把二叉搜索树转换为累加树

问题描述：

Quote

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

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

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

注意：本题和1038.从二叉搜索树到更大和树相同

示例 1：

C++
1
2
输入：[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：

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

示例 3：

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

示例 4：

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

思路分析：

  1. 解法1：中序遍历有序计算和+额外空间

    本题的基本思路是使用中序遍历将结果存放到数组中，再计算该数组的后缀和，将后缀和与原节点进行映射，最后使用对应节点的后缀和覆盖原树的节点即可

  2. 解法2：双指针（遍历时累加）

    在解法1中，将二叉搜索树转换为数组的过程是为了更好得理解从后向前遍历，但是因为转换数组之后节点和元素之和不对应，所以还需要一个哈希表来记录元素和后缀和的映射，导致整个代码的思路虽然清晰，但是空间复杂度比较高。理解了解法1的过程，实际上就可以直接使用双指针在原树上进行修改，但是修改的过程应该是右中左，保证倒序。使用两个指针，其中一个指针表示前一个数值（即已经计算过后缀和的结果），另一个指针就是递归过程中的root，记录当前节点的值，在遍历过程中，当前节点加上前一个节点的数值即可

参考代码：

C++
 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
class Solution538_1
{
public:
    void traversal(TreeNode *root, vector<int> &nums)
    {
        if (!root)
            return;

        traversal(root->left, nums);
        nums.push_back(root->val);
        traversal(root->right, nums);
    }

    vector<int> calSum(const vector<int> &nums)
    {
        vector<int> ret(nums.size());
        partial_sum(nums.rbegin(), nums.rend(), ret.begin());

        return ret;
    }

    void _convertBST(TreeNode *root, unordered_map<int, int> &sum_node)
    {
        if (!root)
            return;

        _convertBST(root->left, sum_node);
        root->val = sum_node[root->val];
        _convertBST(root->right, sum_node);
    }

    void findSum(const vector<int> &nums, const vector<int> &partialSum, unordered_map<int, int> &sum_node)
    {
        for (int i = 0; i < nums.size(); i++)
            sum_node[nums[i]] = partialSum[i];
    }

    TreeNode *convertBST(TreeNode *root)
    {
        vector<int> nums;

        // 获取中序遍历结果
        traversal(root, nums);

        // 找到根节点所在下标
        int rootIndex = 0;
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] == root->val)
                rootIndex = i;

        // 计算后缀和
        vector<int> partialSum = calSum(nums);
        reverse(partialSum.begin(), partialSum.end());

        // 将后缀和与原先树的节点建立映射关系
        unordered_map<int, int> sum_node;
        findSum(nums, partialSum, sum_node);

        // 遍历覆盖原树
        _convertBST(root, sum_node);

        return root;
    }
};
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution538_2
{
public:
    // 使用变量记录前一个节点计算出的总和
    // 使用使用数值记录，防止空指针解引用错误以及额外空指针处理逻辑
    int prev = 0;

    TreeNode *convertBST(TreeNode *root)
    {
        // 节点为空，返回0
        if (!root)
            return 0;

        // 使用右中左遍历
        root->right = convertBST(root->right);
        root->val += prev;
        prev = root->val;
        root->left = convertBST(root->left);

        return root;
    }
};

力扣LCR155.将二叉搜索树转化为排序的双向链表

力扣LCR155.将二叉搜索树转化为排序的双向链表

问题描述：

Quote

将一个二叉搜索树就地转化为一个已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

示例 1：

C++
1
输入：root = [4,2,5,1,3]

C++
1
输出：[1,2,3,4,5]

解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

示例 2：

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

示例 3：

C++
1
2
3
输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。

示例 4：

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

问题描述：

  1. 解法1：异地处理

    异地处理只需要将二叉搜索树进行中序遍历，再根据中序遍历的结果数组创建链表即可

  2. 解法2：双指针（原地处理）

    需要一个节点单独prev记录之前的一个节点，中序遍历过程中，将当前节点的前驱指针指向prev，prev的后继指向当前节点即可完成链接，注意prev不为空的情况，处理完中间的所有节点后，需要额外处理第一个节点和最后一个节点链接

参考代码：

C++
 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
class SolutionLCR155_1
{
public:
    void traversal(Node *root, vector<Node *> &nodes)
    {
        if (!root)
            return;

        traversal(root->left, nodes);
        nodes.push_back(root);
        traversal(root->right, nodes);
    }

    Node *treeToDoublyList(Node *root)
    {
        if (!root)
            return nullptr;

        vector<Node *> nodes;
        traversal(root, nodes);

        // 构建链表
        Node *prev = nullptr;
        Node *dummy = new Node(0);
        for (auto &node: nodes)
        {
            if (!dummy->right)
            {
                dummy->right = node;
                if (nodes.size() == 1)
                {
                    node->left = node;
                    node->right = node;
                    return node;
                }
            }
            else
            {
                dummy->right->left = node;
                node->right = dummy->right;
            }

            if (prev)
            {
                prev->right = node;
                node->left = prev;
            }

            prev = node;
        }

        return dummy->right;
    }
};
C++
 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 SolutionLCR155_2
{
public:
    Node *prev = nullptr;

    void _treeToDoublyList(Node *root)
    {
        if (!root)
            return;

        _treeToDoublyList(root->left);

        root->left = prev;
        if (prev)
            prev->right = root;
        prev = root;

        _treeToDoublyList(root->right);
    }

    Node *treeToDoublyList(Node *root)
    {
        if (!root)
            return nullptr;

        // 找到最左节点作为头节点
        Node *head = root;
        while (head->left)
        {
            head = head->left;
        }

        // 找到头结点后再修改
        // 也可以考虑在找到头结点之前修改
        // 此时就是通过链表向前遍历找到头结点head，而不是通过树的遍历
        _treeToDoublyList(root);

        // 头尾相连
        head->left = prev;
        prev->right = head;

        return head;
    }
};

力扣230.二叉搜索树中第K小的元素

力扣230.二叉搜索树中第K小的元素

问题描述：

Quote

给定一个二叉搜索树的根节点root，和一个整数k，请你设计一个算法查找其中第k小的元素（从1开始计数）。

示例 1：

C++
1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

C++
1
2
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

思路分析：

  1. 解法1：前序遍历+TopK问题（针对一般树解法）

    将元素遍历插入到小堆中，取出第k个小的元素即可

  2. 解法2：中序遍历（利用二叉搜索树中序遍历有序）

    因为二叉搜索树中序遍历结果是升序，所以最小的元素在最前面，第k个小的元素会在第k的位置，只需要通过一个count记录当前遍历的次数即可，再用一个变量minVal记录最小值，本题中将count和minVal设为全局变量最方便。因为一旦找到了第k个较小值，就没必要再遍历后面的节点，此时也可以利用到这个条件进行剪枝

参考代码：

C++
 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
// 不可以使用Lambda作为模版参数
// auto compare = [](TreeNode* root1, TreeNode* root2)->bool{return root1->val > root2->val;};
// using compare = function<bool(TreeNode* root1, TreeNode* root2)>;
// compare cmp = [](TreeNode* root1, TreeNode* root2)->bool{return root1->val > root2->val;};
struct Compare
{
    bool operator()(TreeNode *root1, TreeNode *root2)
    {
        return root1->val > root2->val;
    }
};

class Solution230_1
{
public:
    void dfs(TreeNode *root, priority_queue<TreeNode *, vector<TreeNode *>, Compare> &pq)
    {
        if (!root)
            return;

        pq.push(root);
        dfs(root->left, pq);
        dfs(root->right, pq);
    }

    int kthSmallest(TreeNode *root, int k)
    {
        priority_queue<TreeNode *, vector<TreeNode *>, Compare> pq;
        dfs(root, pq);

        // 弹出k个元素，再取出堆顶元素
        for (int i = 1; i < k; i++)
            pq.pop();

        return pq.top()->val;
    }
};
C++
 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 Solution230_2
{
public:
    int minVal = INT_MAX;
    int count = 0;

    void dfs(TreeNode *root)
    {
        // 如果节点为空或者count为0就不需要向后遍历
        if (!root || !count)
            return;

        dfs(root->left);
        count--;
        // count为0时，说明找到了第k小的元素
        if (count == 0)
            minVal = root->val;
        dfs(root->right);
    }

    int kthSmallest(TreeNode *root, int k)
    {
        count = k;
        dfs(root);

        return minVal;
    }
};