[数据结构与算法]LeetCode 538. Convert BST to Greater Tree - 二叉树（Binary Tree）系列题28

Given the?root?of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a?binary search tree?is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys?less than?the node's key.
• The right subtree of a node contains only nodes with keys?greater than?the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

?

Constraints:

• The number of nodes in the tree is in the range?[0, 104].
• -104?<= Node.val <= 104
• All the values in the tree are?unique.
• root?is guaranteed to be a valid binary search tree.

给定一棵二叉搜索树(Binary Search Tree)，要求把它转换成一棵更大树（Greater Tree）。所谓更大树，就是把原二叉搜索树中的每一个节点值变成它自身值加上原树中比该节点值大的所有节点值的和。

首先来看一下如果给定的是一个数组，如何把数组中每个数变成它自身加上所有比它大的数的总和？其实只要先把数组排序，那么数组中每个数所在位置之后的所有数都是比它大的数，因此只要从后往前进行累加就可以达到目的。

其实二叉树和数组之间是有对应关系的，另外二叉搜索树中序遍历的节点就是从小到大排好序的，而我们要的是从大到小的顺序，其实只要把中序遍历稍作变形即可。在中序遍历算法中先遍历右子树再遍历左子树就是从大到小的顺序了。因此只要在从大到小的遍历的过程中进行累加，更新每个节点值就可以把二叉搜索树转换成更大树。

中序遍历算法有递归和迭代两种：

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        greaterSum = 0
        def helper(node):
            if not node:
                return
            nonlocal greaterSum
            helper(node.right)
            greaterSum += node.val
            node.val = greaterSum
            helper(node.left)
        helper(root)
        
        return root

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        greaterSum = 0
        st = []
        node = root
        while st or node:
            while node:
                st.append(node)
                node = node.right
            node = st.pop()
            node.val += greaterSum
            greaterSum = node.val
            node = node.left
        
        return root