问题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
运行结果: