538. 把二叉搜索树转换为累加树

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/convert-bst-to-greater-tree

题目

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

注意： 本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

解题思路

思路：中序遍历

首先，先审题。题目给定一个二叉搜索树，要将其转换为累加树。这道题与站内 1038 题是一样的，可能本题的一些描述看起来会有些模糊，不妨到 1038 题中看看。

1038. 从二叉搜索树到更大和树

这道题的关键是给定的树是二叉搜索树，这里说下二叉搜索树的概念：

• 左子树不为空时，左子树所有节点值均小于根节点值；
• 右子树不为空，右子树的所有节点值均大于根节点值；
• 左右子树也必须是二叉搜索树。

至于题目中要求转换的累加树，这里题目给出的解释是：使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

根据二叉搜索树的定义，我们知道它的中序遍历输出结果是升序的序列。例如示例：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

中序遍历返回的结果是 [2, 5, 13]

现在题目要求我们在当前节点值的基础上加上所有大于它的节点值之和作为当前节点的新值。

那么我们可以考虑先访问右子树，进行反向中序遍历，那么得到的序列，将是降序排列。那么我们只需要在当前值的基础上，加上序列中前面所有大于它的值作为新值。例如示例（反向中序遍历）

输入: 原始二叉搜索树:
              5
            /   \
           2     13

反向中序遍历得到的结果 [13, 5, 2]。

我们可看到这里节点值递减，那么我们要转换更新值时，只要将当前节点前面的值累加，然后再与当前值相加作为新值即可。

这里的转换过程图示如下：

那么根据上面的分析，整理下思路：

• 处理特殊情况，根节点为空，直接返回；
• 定义变量 total，存储节点值的累加值；
• 反向中序遍历二叉搜索树：
  • 递归右子树，将节点值累加到 total；
  • 然后处理当前节点，先将值累加到 total，然后将 total 作为新值赋给当前节点值；
  • 最后递归左子树，同样将值累加到 total，然后更新值。

具体代码如下。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        # 定义变量，用以存储累加值
        self.total = 0

    def convertBST(self, root: TreeNode) -> TreeNode:

        def dfs(root):
            if not root:
                return

            # 递归右子树
            if root.right:
                dfs(root.right)
            # 递归左子树之前，
            # 先处理值，累加值，并重新赋值给当前节点
            self.total += root.val
            root.val = self.total

            # 递归左子树
            if root.left:
                dfs(root.left)

        dfs(root)
        return root

欢迎关注

公众号 【书所集录】