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

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

 

例如:

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-bst-to-greater-tree

根据题目的意思,所给出的树是二叉搜索树,由二叉搜索树的定义可知,左子树及其子树的值均小于根节点,右子树及其子树的值均大于根节点。根据它的这种特性,当我们使用中序遍历去遍历该树时,我们可以得到一个序列[2, 5, 13] 一个从小到大的排序的序列。
回到该题,该题是要让我们将所有节点的值变为原来其他大于它节点的和,因为正向遍历得到的是从小到大的值,所以我们就反向遍历就能达到从大到小的值,依次累加即可。

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

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        total = 0

        def dfs(node):
            nonlocal total

            if not node:
                return 0
            dfs(node.right)
            tmp = node.val
            node.val += total
            total += tmp
            dfs(node.left)

        dfs(root)
        return root
点赞

发表评论

Title - Artist
0:00