跳到主要内容

33 篇博文 含有标签「树」

查看所有标签

· 阅读需 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

· 阅读需 4 分钟

1、题干​

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

 

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

 

提示：

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

 

注意：本题与主站 124 题相同： https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

2、解题思路​

深度遍历树上所有节点，对每个节点求最大路径和即可。

3、代码​

var maxPathSum = function (root) {
    let res = root.val;
    function dfs(node) {
        if (!node) return -Infinity;
        const maxSum1 = dfs(node.left), maxSum2 = dfs(node.right);
        const maxSum = Math.max(node.val, maxSum1 + node.val, maxSum2 + node.val);
        res = Math.max(res, maxSum, maxSum1, maxSum2, maxSum1 + maxSum2 + node.val);
        return maxSum;
    }
    return dfs(root), res;
};

关键代码说明

  • 求每个节点的最大路径和，且路径不重复的关键
    • const maxSum = Math.max(node.val, maxSum1 + node.val, maxSum2 + node.val);
    • 这行代码用于求当前节点下的最大路径和maxSum，并将其返回给父节点用于计算父节点下的最大路径和
    • Math.max取最大值时包含当前节点的值、当前节点值+左子节点最大路径和、当前节点值+右子节点最大路径和
    • 即最大路径和一定要包含当前节点的值，还可能叠加某个子节点最大路径和，也可能不叠加子节点最大路径和
    • 因此dfs函数逐级返回时，由下至上形成了一条不分叉的路径，并能逐级向上返回子节点的最大路径和
  • 求整棵树最大路径和res的关键
    • res = Math.max(res, maxSum, maxSum1, maxSum2, maxSum1 + maxSum2 + node.val);
    • 在每个节点求最大路径和时，res取其自身以及maxSum1、maxSum2、node.val三者任意组合的路径和中的最大值
    • maxSum1、maxSum2、node.val三者任意组合求和时，至少取1个，且取2个时不能是maxSum1 + maxSum2，因为这个组合不构成路径

4、执行结果​

1.png

· 阅读需 4 分钟

1、题干​

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

 

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

 

提示：

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

 

注意：本题与主站 124 题相同： https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

2、解题思路​

深度遍历树上所有节点，对每个节点求最大路径和即可。

3、代码​

var maxPathSum = function (root) {
    let res = root.val;
    function dfs(node) {
        if (!node) return -Infinity;
        const maxSum1 = dfs(node.left), maxSum2 = dfs(node.right);
        const maxSum = Math.max(node.val, maxSum1 + node.val, maxSum2 + node.val);
        res = Math.max(res, maxSum, maxSum1, maxSum2, maxSum1 + maxSum2 + node.val);
        return maxSum;
    }
    return dfs(root), res;
};

关键代码说明

  • 求每个节点的最大路径和，且路径不重复的关键
    • const maxSum = Math.max(node.val, maxSum1 + node.val, maxSum2 + node.val);
    • 这行代码用于求当前节点下的最大路径和maxSum，并将其返回给父节点用于计算父节点下的最大路径和
    • Math.max取最大值时包含当前节点的值、当前节点值+左子节点最大路径和、当前节点值+右子节点最大路径和
    • 即最大路径和一定要包含当前节点的值，还可能叠加某个子节点最大路径和，也可能不叠加子节点最大路径和
    • 因此dfs函数逐级返回时，由下至上形成了一条不分叉的路径，并能逐级向上返回子节点的最大路径和
  • 求整棵树最大路径和res的关键
    • res = Math.max(res, maxSum, maxSum1, maxSum2, maxSum1 + maxSum2 + node.val);
    • 在每个节点求最大路径和时，res取其自身以及maxSum1、maxSum2、node.val三者任意组合的路径和中的最大值
    • maxSum1、maxSum2、node.val三者任意组合求和时，至少取1个，且取2个时不能是maxSum1 + maxSum2，因为这个组合不构成路径

4、执行结果​

1.png