给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
中序遍历的变化版本
from collections import dequeclass Solution:def convertBST(self, root: TreeNode) -> TreeNode:if root is None:return rootp = rootstack = deque([])tem_sum = 0while stack or p:if p:stack.append(p)p = p.rightelse:p = stack.pop()tem_sum += p.valp.val=tem_sump = p.leftreturn root