奇葩年年有，今年特别多，最近一网友本来打算第二天入职的，结果被通知不用去了，有需求在过去，这明显是被放鸽子了。如果不想要可以提前说，别人也可以继续找，不要等到快入职的时候别人问了才说。网友建议：狠狠骂他，毁offer都这么理直气壮。

网友回复：

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第538题：把二叉搜索树转换为累加树

问题描述

来源：LeetCode第538题

难度：中等

给出 二叉搜索树 的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

示例1：

输入：[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]

  • 树中的节点数介于 0 和 10^4 之间。

  • 每个节点的值介于 -10^4 和 10^4 之间。

  • 树中的所有值 互不相同 。

  • 给定的树为二叉搜索树。

问题分析

这题是让把二叉搜索树中每个节点的值改成所有大于等于该节点值的和，考察的也是二叉搜索树的特性。

如果这题换一种说法，把一个 有序数组 中每个元素变成所有大于等于它的元素和，我们只需要从后往前遍历数组然后累加即可，因为有序数组中每一个元素后面的值都是大于它的。

但这里是一棵二叉搜索树， 二叉搜索树的一个重要特性就是它的中序遍历结果是有序的 ，我们只需要把中序遍历反过来，也就是 先遍历右子树，在访问当前节点，最后在遍历左子树 ，这样就相当于二叉树中所有的节点从大往小的顺序访问，这个时候就可以参考有序数组的操作了。

JAVA：

int sum = 0;// 累加值

public TreeNode convertBST(TreeNode root) {
    if (root == null)
        return null;
    convertBST(root.right);// 递归右子树
    sum += root.val;
    root.val = sum;
    convertBST(root.left);// 递归左子树
    return root;
}

C++：

public:
    int sum = 0;// 累加值
    TreeNode *convertBST(TreeNode *root) {
        if (root == nullptr)
            return nullptr;
        convertBST(root->right);// 递归右子树
        sum += root->val;
        root->val = sum;
        convertBST(root->left);// 递归左子树
        return root;
    }

Python：

def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    s = 0  # 累加值

    def dfs(node):
        if not node:
            return node
        dfs(node.right)  # 递归右子树
        nonlocal s
        s += node.val
        node.val = s
        dfs(node.left)  # 递归左子树
        return node

    dfs(root)
    return root

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。