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

Leetcode Link: 538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

题目

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。

解法一

思路：反中序遍历 由示例1可以看出来，就是我需要先去找到最右下角的节点，然后一点一点求和sum，我们需要在第二次访问节点的时候执行动作。显然这属于中序遍历的逆序。

题解：

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def recur(node):
            nonlocal sum
            if not node:
                sum += 0
                return 
            # 反中序，先右后左
            recur(node.right)
            # 执行累加
            sum = sum + node.val
            node.val = sum
            recur(node.left)
 
        sum = 0 
        recur(root)
        return root

启发和联系

二刷竟然没做出来

错误分析 实际上本题是指针游走，在游走的过程中记录累加和，并无返回值。

而我二刷时，过分依赖左右树的返回值，即我想当然的认为左右树的返回值一定要有，且一定要用上，如node.val=node.val+right来保存当前节点的值，但这只对一部分节点是正确的。

我开始想的是返回当前的累加和，但是左树无法获取当前的累加和，导致一直调不出来。