描述

给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

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

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

示例

示例1：
tree.png

  1. 输入：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
  2. 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例2：

输入：root = [0,null,1]
输出：[1,null,1]

示例3：

输入：root = [1,0,2]
输出：[3,3,2]

示例4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

解题思路

方法一：反序中序遍历

思路及算法

本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

代码

class Solution {
    int sum; 
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        outorder(root);
        return root;
    }
    public void outorder(TreeNode node) {
        if (node == null) return;
        outorder(node.right);
        sum += node.val;
        node.val = sum;
        outorder(node.left);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。