Leetcode 538. 将二叉搜索树转换为累积树
最编程
2024-04-10 12:35:14
...
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 两次遍历即可，第二次必须是中序
res = 0
def dfs1(node):
nonlocal res
if not node:
return
res += node.val
dfs1(node.left)
dfs1(node.right)
dfs1(root)
def dfs2(node):
nonlocal res
if not node:
return
dfs2(node.left)
t = res - node.val
node.val = res
res = t
dfs2(node.right)
dfs2(root)
return root