LeetCode 538：二叉搜索树转换为累加树

LeetCode538给出二叉搜索树的根节点root该树的节点值各不相同请你将其转换为累加树Greater Sum Tree将其转换为一个更大的树使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。示例输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]Python解法DFS# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: total 0 def dfs(node): nonlocal total if node: # 1. 先遍历右子树更大的数 dfs(node.right) # 2. 处理当前节点累加、更新值 total node.val node.val total # 3. 遍历左子树更小的数 dfs(node.left) dfs(root) return rootJava解法class Solution { int sum 0; public TreeNode convertBST(TreeNode root) { dfs(root); return root; } void dfs(TreeNode node) { if(node null) return; dfs(node.right); sum node.val; node.val sum; dfs(node.left); } }C解法class Solution { public: int total 0; TreeNode* convertBST(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* node) { if(!node) return; dfs(node-right); total node-val; node-val total; dfs(node-left); } };