31 篇博文含有标签「二叉树」

查看所有标签

LCR 054.把二叉搜索树转换为累加树

2022年1月6日 · 阅读需 3 分钟

Whilconn

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 和 10⁴之间。
每个节点的值介于 -10⁴ 和 10⁴ 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

注意：

本题与主站 538 题相同： https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
本题与主站 1038 题相同：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/

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)$

5、执行结果

剑指 Offer II 054.所有大于等于节点的值之和

2022年1月6日 · 阅读需 3 分钟

Whilconn

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 和 10⁴之间。
每个节点的值介于 -10⁴ 和 10⁴ 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

注意：

本题与主站 538 题相同： https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
本题与主站 1038 题相同：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/

2、解题思路

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

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)$

5、执行结果

LCR 053.二叉搜索树中的中序后继

2022年1月3日 · 阅读需 2 分钟

Whilconn

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, 10⁴] 内。
-10⁵ <= Node.val <= 10⁵
树中各节点的值均保证唯一。

注意：本题与主站 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、执行结果

剑指 Offer II 053.二叉搜索树中的中序后继

2022年1月3日 · 阅读需 2 分钟

Whilconn

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, 10⁴] 内。
-10⁵ <= Node.val <= 10⁵
树中各节点的值均保证唯一。

注意：本题与主站 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、执行结果

LCR 052.递增顺序搜索树

2022年1月1日 · 阅读需 3 分钟

Whilconn

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、执行结果

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

剑指 Offer II 052.展平二叉搜索树

2022年1月1日 · 阅读需 3 分钟

Whilconn

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+改变指针

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、执行结果

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

LCR 051.二叉树中的最大路径和

2021年12月30日 · 阅读需 4 分钟

Whilconn

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 * 10⁴]
-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、执行结果

剑指 Offer II 051.节点之和最大的路径

2021年12月30日 · 阅读需 4 分钟

Whilconn

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 * 10⁴]
-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、执行结果

LCR 050.路径总和 III

2021年12月29日 · 阅读需 4 分钟

Whilconn

1、题干

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

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

提示:

二叉树的节点个数的范围是 [0,1000]
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

注意：本题与主站 437 题相同：https://leetcode-cn.com/problems/path-sum-iii/

2、解法1

使用DFS递归遍历树的所有节点，递归函数接收上层传递下来的路径上所有前缀和，遍历所有前缀和并计算是否存在和等于targetSum的路径（计算公式node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum），存在则最终结果+1，时间复杂度为 $O(nlogn)$ 。

上述时间复杂度是估算值，因为每个节点需要访问一次，因此至少有 $O(n)$ 的复杂度，另外每个节点内部需要再遍历前缀和数组，而数组长度最大为树的最大高度 $logn$ ，因此综合估算时间复杂度为 $O(nlogn)$ 。

3、代码

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = root.val === targetSum ? 1 : 0;

    function dfs(node, sums) {
        if (!node) return;
        for (let i = -1; i < sums.length; i++) {
            if (node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum) res++;
        }

        dfs(node.left, [...sums, (sums[sums.length - 1] || 0) + node.val]);
        dfs(node.right, [...sums, (sums[sums.length - 1] || 0) + node.val]);
    }

    return dfs(root, []), res;
};

4、执行结果

执行用时: 148 ms 内存消耗: 57.8 MB

5、解法2

该解法是解法1的优化版本，利用了哈希表存储前缀和，另外使用了回溯的思想重置前缀和状态，优化后的时间复杂度为 $O(n)$ 。

同样使用DFS递归遍历树的所有节点，但使用Map存储前缀和及其数量，递归时在Map中查找是否已存在等于sum - targetSum的路径前缀和，存在则最终结果累加其数量
将当前路径总和对应的数量累加1
然后进入下层递归，同样执行上述逻辑
下层递归结束时，将当前路径总和对应的数量累减1

6、代码

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = 0, map = new Map();
    map.set(0, 1);

    function dfs(node, sum) {
        if (!node) return;
        sum = sum + node.val;
        res += map.get(sum - targetSum) || 0;
        map.set(sum, (map.get(sum) || 0) + 1);
        dfs(node.left, sum);
        dfs(node.right, sum);
        map.set(sum, map.get(sum) - 1);
    }

    return dfs(root, 0), res;
};

7、执行结果

剑指 Offer II 050.向下的路径节点之和

2021年12月29日 · 阅读需 4 分钟

Whilconn

1、题干

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

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

提示:

二叉树的节点个数的范围是 [0,1000]
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

注意：本题与主站 437 题相同：https://leetcode-cn.com/problems/path-sum-iii/

2、解法1

上述时间复杂度是估算值，因为每个节点需要访问一次，因此至少有 $O(n)$ 的复杂度，另外每个节点内部需要再遍历前缀和数组，而数组长度最大为树的最大高度 $logn$ ，因此综合估算时间复杂度为 $O(nlogn)$ 。

3、代码

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = root.val === targetSum ? 1 : 0;

    function dfs(node, sums) {
        if (!node) return;
        for (let i = -1; i < sums.length; i++) {
            if (node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum) res++;
        }

        dfs(node.left, [...sums, (sums[sums.length - 1] || 0) + node.val]);
        dfs(node.right, [...sums, (sums[sums.length - 1] || 0) + node.val]);
    }

    return dfs(root, []), res;
};

4、执行结果

执行用时: 148 ms 内存消耗: 57.8 MB

5、解法2

该解法是解法1的优化版本，利用了哈希表存储前缀和，另外使用了回溯的思想重置前缀和状态，优化后的时间复杂度为 $O(n)$ 。

同样使用DFS递归遍历树的所有节点，但使用Map存储前缀和及其数量，递归时在Map中查找是否已存在等于sum - targetSum的路径前缀和，存在则最终结果累加其数量
将当前路径总和对应的数量累加1
然后进入下层递归，同样执行上述逻辑
下层递归结束时，将当前路径总和对应的数量累减1

6、代码

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = 0, map = new Map();
    map.set(0, 1);

    function dfs(node, sum) {
        if (!node) return;
        sum = sum + node.val;
        res += map.get(sum - targetSum) || 0;
        map.set(sum, (map.get(sum) || 0) + 1);
        dfs(node.left, sum);
        dfs(node.right, sum);
        map.set(sum, map.get(sum) - 1);
    }

    return dfs(root, 0), res;
};

1、题干​

2、解题思路​

3、代码​

4、复杂度​

5、执行结果​

1、题干​

2、解题思路​

3、代码​

4、复杂度​

5、执行结果​

1、题干​

2、解题思路​

3、代码​

4、执行结果​

1、题干​

2、解题思路​

3、代码​

4、执行结果​

1、题干​

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

3、代码​

4、执行结果​

5、解法2-DFS+数组​

6、代码​

7、执行结果​

1、题干​

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

3、代码​

4、执行结果​

5、解法2-DFS+数组​

6、代码​

7、执行结果​

1、题干​

2、解题思路​

3、代码​

4、执行结果​

1、题干​

2、解题思路​

3、代码​

4、执行结果​

1、题干​

2、解法1​

3、代码​

4、执行结果​

5、解法2​

6、代码​

7、执行结果​

1、题干​

2、解法1​

3、代码​

4、执行结果​

5、解法2​

6、代码​

7、执行结果​

1、题干

2、解题思路

3、代码

4、复杂度

5、执行结果

1、题干

2、解题思路

3、代码

4、复杂度

5、执行结果

1、题干

2、解题思路

3、代码

4、执行结果

1、题干

2、解题思路

3、代码

4、执行结果

1、题干

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

3、代码

4、执行结果

5、解法2-DFS+数组

6、代码

7、执行结果

1、题干

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

3、代码

4、执行结果

5、解法2-DFS+数组

6、代码

7、执行结果

1、题干

2、解题思路

3、代码

4、执行结果

1、题干

2、解题思路

3、代码

4、执行结果

1、题干

2、解法1

3、代码

4、执行结果

5、解法2

6、代码

7、执行结果

1、题干

2、解法1

3、代码

4、执行结果

5、解法2

6、代码

7、执行结果