Medium

题目描述

给定一个二叉搜索树（BST）的根节点，将其转换为累加树，使得原 BST 中每个节点的键值都被替换为原键值加上所有大于原键值的节点值之和。

提醒一下，二叉搜索树是满足以下约束条件的树：

  • 节点的左子树只包含键值小于节点键值的节点。
  • 节点的右子树只包含键值大于节点键值的节点。
  • 左右子树也都必须是二叉搜索树。

示例 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]

约束条件：

  • 树中节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 100
  • 树中所有值都是唯一的

注意： 此题与题目 538 相同：https://leetcode.com/problems/convert-bst-to-greater-tree/

解题思路

这道题的关键是要理解二叉搜索树的性质：中序遍历可以得到递增序列。

由于我们需要将每个节点的值替换为原值加上所有比它大的值的和，可以使用反向中序遍历（右-根-左）来解决。

核心思路：

  1. 反向中序遍历会按从大到小的顺序访问节点
  2. 维护一个累加和变量，记录已访问节点的累计和
  3. 对于当前节点，将其值更新为原值加上累加和，然后更新累加和

算法步骤：

  1. 先递归遍历右子树（获取所有更大的值）
  2. 处理当前节点：更新节点值为原值+累加和，更新累加和
  3. 再递归遍历左子树

这样可以保证访问每个节点时，所有比它大的节点都已经被处理过，累加和就是所有比当前节点大的值的总和。

时间复杂度O(n)，空间复杂度O(h)，其中h为树的高度。

代码实现

class Solution {
private:
    int sum = 0;
    
    void traverse(TreeNode* node) {
        if (!node) return;
        
        // 先遍历右子树
        traverse(node->right);
        
        // 处理当前节点
        sum += node->val;
        node->val = sum;
        
        // 再遍历左子树
        traverse(node->left);
    }
    
public:
    TreeNode* bstToGst(TreeNode* root) {
        traverse(root);
        return root;
    }
};

class Solution:
    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.sum = 0
        
        def traverse(node):
            if not node:
                return
            
            # 先遍历右子树
            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 BstToGst(TreeNode root) {
        Traverse(root);
        return root;
    }
    
    private void Traverse(TreeNode node) {
        if (node == null) return;
        
        // 先遍历右子树
        Traverse(node.right);
        
        // 处理当前节点
        sum += node.val;
        node.val = sum;
        
        // 再遍历左子树
        Traverse(node.left);
    }
}

var bstToGst = function(root) {
    let sum = 0;
    
    function traverse(node) {
        if (!node) return;
        
        // 先遍历右子树
        traverse(node.right);
        
        // 处理当前节点
        sum += node.val;
        node.val = sum;
        
        // 再遍历左子树
        traverse(node.left);
    }
    
    traverse(root);
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要访问树中的每个节点一次，其中n为节点总数
空间复杂度O(h)递归调用栈的深度等于树的高度h，最坏情况下为O(n)