您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode如何把二叉搜索树转换为累加树
## 问题背景与定义
### 什么是二叉搜索树（BST）？
二叉搜索树（Binary Search Tree）是一种特殊的二叉树数据结构，满足以下性质：
- 左子树所有节点的值小于根节点的值
- 右子树所有节点的值大于根节点的值
- 左右子树也必须是二叉搜索树
### 什么是累加树（Greater Tree）？
累加树是指将二叉搜索树的每个节点值替换为**原树中所有大于或等于该节点值的和**。例如：
原始BST:
5
/
2 13
转换为累加树:
18
/
20 13
### LeetCode题目描述
[LeetCode 538](https://leetcode.com/problems/convert-bst-to-greater-tree/)题目要求：
给定一个二叉搜索树的根节点，将其转换为累加树，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
## 基础解法分析
### 暴力解法（不推荐）
1. **遍历+排序**：中序遍历获取所有节点值并排序
2. **计算前缀和**：对每个节点重新计算累加值
3. **时间复杂度**：O(n^2)，空间复杂度O(n)
```python
# 伪代码示例
def convertBST(root):
nodes = inorder_traversal(root)
sorted_nodes = sorted(nodes, reverse=True)
prefix_sum = 0
for node in nodes:
node.val += sum(x for x in sorted_nodes if x > node.val)
return root
关键观察：BST的中序遍历是升序序列，那么逆中序遍历就是降序序列。可以在遍历过程中维护一个累加变量。
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.total = 0
def traverse(node):
if not node:
return
traverse(node.right) # 先访问右子树
self.total += node.val
node.val = self.total # 更新当前节点值
traverse(node.left) # 最后访问左子树
traverse(root)
return root
时间复杂度：O(n)
空间复杂度：O(h)，h为树高（递归栈空间）
使用显式栈替代递归，避免栈溢出风险：
def convertBST(root):
total = 0
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.right
node = stack.pop()
total += node.val
node.val = total
node = node.left
return root
优化空间复杂度到O(1)：
def convertBST(root):
total = 0
current = root
while current:
if not current.right:
total += current.val
current.val = total
current = current.left
else:
# 找到当前节点的前驱节点
predecessor = current.right
while predecessor.left and predecessor.left != current:
predecessor = predecessor.left
if not predecessor.left:
predecessor.left = current
current = current.right
else:
predecessor.left = None
total += current.val
current.val = total
current = current.left
return root
| 测试案例 | 说明 |
|---|---|
| 空树 | 输入None，返回None |
| 单节点树 | 节点值不变 |
| 完全左斜树 | 每个节点累加上所有右祖先节点 |
| 完全右斜树 | 节点值依次累加 |
| 标准BST | 常规测试 |
# 处理负数值的BST
[-3,-4,0,None,None,-2,1] → [ -6,-10,1,None,None,-1,1 ]
# 处理大数溢出（题目通常限制在32位整数范围内）
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力解法 | O(n^2) | O(n) | 仅用于理解问题 |
| 递归逆中序遍历 | O(n) | O(h) | 大多数情况 |
| 迭代逆中序遍历 | O(n) | O(h) | 深度较大的树 |
| Morris遍历 | O(n) | O(1) | 内存严格受限环境 |
对于普通二叉树，需要先进行排序操作，时间复杂度升至O(nlogn)
对于超大型BST： 1. 将树分割为子树 2. 并行计算子树的和 3. 合并结果时需要同步机制
Q: 为什么选择逆中序遍历？
A: 因为BST的中序遍历是升序，逆序后可以按从大到小顺序累加
Q: 如何处理重复节点值？
A: 题目定义中”大于或等于”包含等于情况，重复值需要多次累加
Q: 能否用前序/后序遍历解决？
A: 不能，必须保证访问顺序是从大到小
解决BST转累加树的核心在于： 1. 理解BST的中序特性 2. 逆向遍历的妙用 3. 维护累加变量的技巧
最佳实践是使用时间复杂度O(n)、空间复杂度O(h)的逆中序遍历方法，在面试中建议同时给出递归和迭代两种实现。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
# 递归版本
def convertBST_recursive(self, root: TreeNode) -> TreeNode:
self.total = 0
def helper(node):
if not node:
return
helper(node.right)
self.total += node.val
node.val = self.total
helper(node.left)
helper(root)
return root
# 迭代版本
def convertBST_iterative(self, root: TreeNode) -> TreeNode:
total = 0
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.right
node = stack.pop()
total += node.val
node.val = total
node = node.left
return root
”`
（注：实际字符数约2400字，可根据需要增减细节部分调整到精确字数）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。