跳到主要内容

10 篇博文 含有标签「二叉搜索树」

查看所有标签

· 阅读需 2 分钟

1、题干​

给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

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

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

 

示例 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]

 

提示：

  • 树中的节点数在 [1, 100] 范围内。
  • 0 <= Node.val <= 100
  • 树中的所有值均 不重复 。

 

注意：该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/  相同

2、思路​

根据题意使用DFS模拟，需要注意：

  • 对左子节点求和，需要将父节点求和结果、右子树节点之和、自身数值3者累加
  • 对右子节点求和，需要将右边祖先节点求和结果、右子树节点之和、自身数值3者累加

3、代码​

function bstToGst(root: TreeNode | null): TreeNode | null {
    return dfs(root), root;
}

function dfs(root?: TreeNode, pSum = 0): number {
    if (!root) return 0;

    const val = root.val;
    const rSum = dfs(root.right, pSum);
    root.val = val + pSum + rSum;
    const lSum = dfs(root.left, root.val);

    return val + rSum + lSum;
}

· 阅读需 4 分钟

1、题干​

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

 

示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

提示：

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104 次
  • 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

 

注意：本题与主站 703 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

2、解法1-优先队列​

使用优先队列解题，初始化时把所有元素加入到最小优先队列pq中，添加元素时直接把元素加入pq，若pq元素个数小于k则直接返回-1，若pq元素个数超过k则逐一移除最后返回队头元素。


3、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.pq = new MinPriorityQueue({ compare: (a, b) => a - b });
    for (const n of nums) this.pq.enqueue(n);
};

KthLargest.prototype.add = function (val) {
    this.pq.enqueue(val);
    if (this.pq.size() < this.k) return -1;
    while (this.pq.size() > this.k) this.pq.dequeue();
    return this.pq.front();
};

4、复杂度​

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

5、执行结果​

执行用时: 132 ms 内存消耗: 46.6 MB


6、解法2-计数排序​

对数据流使用计数排序，首次确定第 k 大元素 kIdx 需要遍历所有元素；此后添加数据需要再确定第 k 大元素时，如果添加的数据比 kIdx 小则直接返回 kIdx ；如果添加的数据比 kIdx 小则从下标 kIdx 开始在容器 list 找到更大且元素值不为0的下标返回即可。


这个题目中使用该算法坑略多，只作参考，不建议使用。


7、复杂度​

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

8、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.size = nums.length;
    this.kIdx = -1;
    this.list = new Array(2e4 + 1).fill(0);
    for (const n of nums) this.list[n + 1e4]++;
};

KthLargest.prototype.add = function (val) {
    (val += 1e4), this.list[val]++, this.size++;
    if (this.size < this.k) return -1;

    if (this.kIdx < 0) {
        for (let i = this.list.length - 1, k = this.k; i >= 0; i--) {
            if (k < this.list[i]) this.list[i] = k;
            if ((k -= this.list[i]) <= 0) {
                this.kIdx = i;
                break;
            }
        }
        return this.kIdx - 1e4;
    }

    if (this.size > this.k && val >= this.kIdx) {
        this.list[this.kIdx]--;
        for (let i = this.kIdx; i < this.list.length; i++) {
            if (this.list[i]) {
                this.kIdx = i;
                break;
            }
        }
    }

    return this.kIdx - 1e4;
};

9、执行结果​

1.png

· 阅读需 4 分钟

1、题干​

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

 

示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

提示：

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104 次
  • 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

 

注意：本题与主站 703 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

2、解法1-优先队列​

使用优先队列解题，初始化时把所有元素加入到最小优先队列pq中，添加元素时直接把元素加入pq，若pq元素个数小于k则直接返回-1，若pq元素个数超过k则逐一移除最后返回队头元素。


3、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.pq = new MinPriorityQueue({ compare: (a, b) => a - b });
    for (const n of nums) this.pq.enqueue(n);
};

KthLargest.prototype.add = function (val) {
    this.pq.enqueue(val);
    if (this.pq.size() < this.k) return -1;
    while (this.pq.size() > this.k) this.pq.dequeue();
    return this.pq.front();
};

4、复杂度​

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

5、执行结果​

执行用时: 132 ms 内存消耗: 46.6 MB


6、解法2-计数排序​

对数据流使用计数排序，首次确定第 k 大元素 kIdx 需要遍历所有元素；此后添加数据需要再确定第 k 大元素时，如果添加的数据比 kIdx 小则直接返回 kIdx ；如果添加的数据比 kIdx 小则从下标 kIdx 开始在容器 list 找到更大且元素值不为0的下标返回即可。


这个题目中使用该算法坑略多，只作参考，不建议使用。


7、复杂度​

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

8、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.size = nums.length;
    this.kIdx = -1;
    this.list = new Array(2e4 + 1).fill(0);
    for (const n of nums) this.list[n + 1e4]++;
};

KthLargest.prototype.add = function (val) {
    (val += 1e4), this.list[val]++, this.size++;
    if (this.size < this.k) return -1;

    if (this.kIdx < 0) {
        for (let i = this.list.length - 1, k = this.k; i >= 0; i--) {
            if (k < this.list[i]) this.list[i] = k;
            if ((k -= this.list[i]) <= 0) {
                this.kIdx = i;
                break;
            }
        }
        return this.kIdx - 1e4;
    }

    if (this.size > this.k && val >= this.kIdx) {
        this.list[this.kIdx]--;
        for (let i = this.kIdx; i < this.list.length; i++) {
            if (this.list[i]) {
                this.kIdx = i;
                break;
            }
        }
    }

    return this.kIdx - 1e4;
};

9、执行结果​

1.png

· 阅读需 3 分钟

1、题干​

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

 

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

 

提示：

  • 二叉树的节点个数的范围是  [1, 104].
  • -104 <= Node.val <= 104
  • root 为二叉搜索树
  • -105 <= k <= 105

 

注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

2、解法1​

DFS遍历+哈希查找：DFS遍历所有节点node，在哈希表set中查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

3、代码​

var findTarget = function (root, k) {
    const set = new Set();
    function dfs(node) {
        if (!node) return false;
        if (set.has(k - node.val)) return true;
        set.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
};

4、复杂度​

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

5、执行结果​

1.png


6、解法2​

DFS遍历+DFS二分查找：DFS遍历所有节点node，利用BST特性进行DFS二分查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

这里二分搜索的时间复杂度受到二叉树平衡性的影响，最坏情况下二叉树可能退化成链表，导致搜索时间复杂度为O(n)O(n)，总体时间复杂度为O(n2)O(n^2)

7、代码​

var findTarget = function (root, k) {
    function find(node, num) {
        if (!node) return false;
        if (num === node.val) return true;
        return num > node.val ? find(node.right, num) : find(node.left, num);
    }

    function findSum(node, num) {
        if (!node) return false;
        return (num !== 2 * node.val && find(root, num - node.val)) || findSum(node.right, num) || findSum(node.left, num);
    }

    return findSum(root, k);
};

8、复杂度​

时间复杂度：平衡二叉搜索树的情况下为O(nlogn)O(nlogn) ，非平衡二叉搜索树的情况下超过O(nlogn)O(nlogn)，最差为O(n2)O(n^2)

空间复杂度：O(1)O(1)

9、执行结果​

1.png

· 阅读需 3 分钟

1、题干​

给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

 

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

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

 

示例 1：

输入：root = [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 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

 

注意：

2、解题思路​

按中序相反的顺序（右子节点、父节点、左子节点）深度遍历所有节点，所有节点将会从大到小依次被访问，遍历过程中利用前缀和思想叠加节点之和，将当前节点值修改为前缀和加自身值presum + node.val即可。

如果不好理解，可以使用中序遍历所有节点并将节点依次存入数组，这样数组中的节点是按照值的大小升序排列，然后再倒序遍历数组并累加节点值、修改节点值即可。


3、代码​

var convertBST = function (root) {
    let presum = 0;
    function dfs(node) {
        if (!node) return;
        dfs(node.right);
        node.val = (presum += node.val);
        dfs(node.left, node.val);
    }
    return dfs(root), root;
};

4、复杂度​

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

5、执行结果​

1.png

· 阅读需 3 分钟

1、题干​

给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

 

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

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

 

示例 1：

输入：root = [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 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

 

注意：

2、解题思路​

按中序相反的顺序（右子节点、父节点、左子节点）深度遍历所有节点，所有节点将会从大到小依次被访问，遍历过程中利用前缀和思想叠加节点之和，将当前节点值修改为前缀和加自身值presum + node.val即可。

如果不好理解，可以使用中序遍历所有节点并将节点依次存入数组，这样数组中的节点是按照值的大小升序排列，然后再倒序遍历数组并累加节点值、修改节点值即可。


3、代码​

var convertBST = function (root) {
    let presum = 0;
    function dfs(node) {
        if (!node) return;
        dfs(node.right);
        node.val = (presum += node.val);
        dfs(node.left, node.val);
    }
    return dfs(root), root;
};

4、复杂度​

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

5、执行结果​

1.png

· 阅读需 2 分钟

1、题干​

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

 

示例 1：

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

 

提示：

  • 树中节点的数目在范围 [1, 104] 内。
  • -105 <= Node.val <= 105
  • 树中各节点的值均保证唯一。

 

注意：本题与主站 285 题相同： https://leetcode-cn.com/problems/inorder-successor-in-bst/

2、解题思路​

中序遍历记录前一节点pre，若前一节点与p引用相同，则当前节点node就是p的中序后继，记为res即最终返回结果。

3、代码​

var inorderSuccessor = function (root, p) {
    let pre, res = null;
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        if (pre === p) res = node;
        pre = node;
        dfs(node.right);
    }
    return dfs(root), res;
};

4、执行结果​

1.png

· 阅读需 2 分钟

1、题干​

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

 

示例 1：

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

 

提示：

  • 树中节点的数目在范围 [1, 104] 内。
  • -105 <= Node.val <= 105
  • 树中各节点的值均保证唯一。

 

注意：本题与主站 285 题相同： https://leetcode-cn.com/problems/inorder-successor-in-bst/

2、解题思路​

中序遍历记录前一节点pre，若前一节点与p引用相同，则当前节点node就是p的中序后继，记为res即最终返回结果。

3、代码​

var inorderSuccessor = function (root, p) {
    let pre, res = null;
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        if (pre === p) res = node;
        pre = node;
        dfs(node.right);
    }
    return dfs(root), res;
};

4、执行结果​

1.png

· 阅读需 3 分钟

1、题干​

给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

 

示例 1：

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

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

 

提示：

  • 树中节点数的取值范围是 [1, 100]
  • 0 <= Node.val <= 1000

 

注意：本题与主站 897 题相同： https://leetcode-cn.com/problems/increasing-order-search-tree/

2、解法1-DFS+改变指针​

深度遍历所有节点，在递归左子节点后构造新的二叉树，newRoot用于记录新树的根节点，若newRoot为空则赋值为当前节点，lastNode用于记录新树的最后一个节点，若lastNode有值则将其右子节点置为当前节点，然后将lastNode置为当前节点，当前节点的左子节点置为空，最后返回newRoot

3、代码​

var increasingBST = function (root) {
    let newRoot = null, lastNode = null;
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        if (!newRoot) newRoot = node;
        if (lastNode) lastNode.right = node;
        lastNode = node;
        node.left = null;
        dfs(node.right);
    }
    dfs(root);

    return newRoot;
};

4、执行结果​

1.png

5、解法2-DFS+数组​

深度遍历将节点按中序存入数组中，结束后对节点数组进行遍历，将当前节点的左子节点置空右子节点置为下一个数组元素，最后返回数组首个元素。

6、代码​

var increasingBST = function (root) {
    const arr = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        arr.push(node);
        dfs(node.right);
    }
    dfs(root);

    for (let i = 0; i < arr.length; i++) {
        arr[i].left = null;
        arr[i].right = arr[i + 1] || null;
    }

    return arr[0];
};

7、执行结果​

执行用时: 68 ms 内存消耗: 39.2 MB

· 阅读需 3 分钟

1、题干​

给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

 

示例 1：

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

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

 

提示：

  • 树中节点数的取值范围是 [1, 100]
  • 0 <= Node.val <= 1000

 

注意：本题与主站 897 题相同： https://leetcode-cn.com/problems/increasing-order-search-tree/

2、解法1-DFS+改变指针​

深度遍历所有节点，在递归左子节点后构造新的二叉树，newRoot用于记录新树的根节点，若newRoot为空则赋值为当前节点，lastNode用于记录新树的最后一个节点，若lastNode有值则将其右子节点置为当前节点，然后将lastNode置为当前节点，当前节点的左子节点置为空，最后返回newRoot

3、代码​

var increasingBST = function (root) {
    let newRoot = null, lastNode = null;
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        if (!newRoot) newRoot = node;
        if (lastNode) lastNode.right = node;
        lastNode = node;
        node.left = null;
        dfs(node.right);
    }
    dfs(root);

    return newRoot;
};

4、执行结果​

1.png

5、解法2-DFS+数组​

深度遍历将节点按中序存入数组中，结束后对节点数组进行遍历，将当前节点的左子节点置空右子节点置为下一个数组元素，最后返回数组首个元素。

6、代码​

var increasingBST = function (root) {
    const arr = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        arr.push(node);
        dfs(node.right);
    }
    dfs(root);

    for (let i = 0; i < arr.length; i++) {
        arr[i].left = null;
        arr[i].right = arr[i + 1] || null;
    }

    return arr[0];
};

7、执行结果​

执行用时: 68 ms 内存消耗: 39.2 MB