LeetCode 题解工作台
从二叉搜索树到更大和树
给定一个二叉搜索树 root (BST) ，请将它的每个 节点 的值替换成树中大于或者等于该 节点 值的所有 节点 值之和。 提醒一下， 二叉搜索树 满足下列约束条件： 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 示例 1： …
4
题型
8
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
按照“右根左”的顺序，递归遍历二叉搜索树，累加遍历到的所有节点值到 中，然后每次赋值给对应的 `node` 节点。 时间复杂度 ，空间复杂度 。其中 是二叉搜索树的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉搜索树 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/problems/convert-bst-to-greater-tree/ 相同
解题思路
方法一：递归
按照“右根左”的顺序，递归遍历二叉搜索树，累加遍历到的所有节点值到 中，然后每次赋值给对应的 node 节点。
时间复杂度 ，空间复杂度 。其中 是二叉搜索树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root: Optional[TreeNode]):
if root is None:
return
dfs(root.right)
nonlocal s
s += root.val
root.val = s
dfs(root.left)
s = 0
dfs(root)
return root
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each node is visited exactly once. Space complexity is O(1) if ignoring recursion stack or O(h) with recursive DFS, where h is the tree height. The in-place update avoids extra arrays for storing node values. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Expect a clear reverse in-order DFS approach that handles cumulative sums correctly.
- question_mark
Watch for correct in-place updates without changing tree structure.
- question_mark
Demonstrate understanding of BST properties and traversal order impact.
常见陷阱
外企场景- error
Traversing in standard in-order instead of reverse, which miscalculates cumulative sums.
- error
Resetting the running sum incorrectly between recursive calls or iterations.
- error
Using extra space unnecessarily to store node values instead of updating in-place.
进阶变体
外企场景- arrow_right_alt
Convert a BST to a Lesser Sum Tree by accumulating all smaller node values using in-order traversal.
- arrow_right_alt
Handle BSTs with duplicate values where the greater-sum rule includes duplicates differently.
- arrow_right_alt
Implement the transformation iteratively using Morris traversal to achieve O(1) extra space.