Medium
题目描述
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键小于节点键的节点。
- 节点的右子树仅包含键大于节点键的节点。
- 左右子树也必须是二叉搜索树。
示例 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]
约束条件：
- 树中的节点数介于
0和10^4之间。 -10^4 <= Node.val <= 10^4- 树中的所有值互不相同。
root是二叉搜索树的有效根节点。
解题思路
这道题的关键在于利用二叉搜索树的性质。在BST中，右子树的所有节点都大于当前节点，左子树的所有节点都小于当前节点。
核心思路：反向中序遍历
传统的中序遍历是"左-根-右"，会得到升序序列。而我们需要累加大于当前节点的所有值，因此采用"右-根-左"的反向中序遍历，这样就能从大到小访问节点。
算法步骤：
- 维护一个累加和变量，记录已访问的较大节点值的总和
- 采用反向中序遍历（右-根-左）
- 访问每个节点时，将当前节点值加到累加和中
- 将累加和赋值给当前节点，实现转换
这种方法只需要一次遍历，时间复杂度为O(n)，空间复杂度为O(h)（递归栈深度，h为树高）。
递归实现：使用全局变量或成员变量维护累加和，递归过程中更新节点值。
迭代实现：使用栈模拟递归过程，同样按照"右-根-左"的顺序处理节点。
代码实现
class Solution {
private:
int sum = 0;
public:
TreeNode* convertBST(TreeNode* root) {
if (root) {
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
};
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.sum = 0
def traverse(node):
if node:
traverse(node.right)
self.sum += node.val
node.val = self.sum
traverse(node.left)
traverse(root)
return root
public class Solution {
private int sum = 0;
public TreeNode ConvertBST(TreeNode root) {
if (root != null) {
ConvertBST(root.right);
sum += root.val;
root.val = sum;
ConvertBST(root.left);
}
return root;
}
}
var convertBST = function(root) {
let sum = 0;
function traverse(node) {
if (node) {
traverse(node.right);
sum += node.val;
node.val = sum;
traverse(node.left);
}
}
traverse(root);
return root;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要访问每个节点一次，n为节点总数 |
| 空间复杂度 | O(h) | 递归调用栈的深度，h为树的高度。最坏情况下为O(n)（完全不平衡树），最好情况下为O(log n)（平衡树） |