LeetCode问题538:BST每个节点的值加上比它大的节点的值

问题538:给定一个二叉搜索树,把它转换成为累加树,使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

这题对二叉树进行右-中-左遍历,将值累加即可。

完整代码:

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

运行结果:

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。