.jpg)
492 字
2 分钟
把二叉搜索树转换为累加树
.jpg)
题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
解题思路
- 逆中序遍历：
- 反向中序遍历（右→根→左）
- 按降序访问节点值
- 累加机制：
- 维护全局累加变量 sum
- 每个节点新值 = 原值 + 当前 sum
- 更新 sum = 新节点值
- 递归实现：
- 先递归右子树
- 处理当前节点
- 再递归左子树
- 就地修改：
- 直接在原树节点更新值
- 无需创建新树
关键洞察
- 降序访问原理：
- BST特性：右子树值 > 根值 > 左子树值
- 右子树优先访问保证降序遍历
- 累加传递性：
- 大值节点先被访问并累加
- 小值节点继承大值累加结果
- 状态维护：
- 全局 sum 记录已访问节点值总和
- 每个节点只需访问一次
- 无新树创建：
- 直接修改节点值
- 保持原树结构不变
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：每个节点访问一次 |
| 空间复杂度 | O(h)：递归栈深度（h为树高，最坏O(n)） |
代码实现
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {TreeNode} */var convertBST = function (root) { const stack = []; let sum = 0; let node = root; while (stack.length || node) { while (node) { stack.push(node); node = node.right } node = stack.pop(); sum += node.val; node.val = sum; node = node.left; } return root;};相似题目
- 无