本文共 3439 字,大约阅读时间需要 11 分钟。
Given the root of a binary search tree with distinct values, modify it so that every node
has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val
.
As a reminder, a binary search tree is a tree that satisfies these constraints:
Example 1:
Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Note:
1
and 100
.0
and 100
.我的解题思路是:
首先计算出大于或等于原根节点的值,然后我们可以发现,对此根节点来说,它右边的部分的节点计算只需要减去它的父节点的节点值,然后如果有左孩子,再减去左孩子的和就是大于或等于它的值。
对于原根节点的左部分来说(注意是原根节点),每个节点的更新是父节点的值加上自己根节点的值,如果有右孩子,还要加上右孩子部分的和。
具体的更新看代码可能更明白一些。
更新:一个更明了的方法
对每个节点来说,大于或等于他的值的和都是,它如果是左孩子,就是本身的值加上右子树的值加上父节点的值加上父节点右子树的值,如果节点是右孩子,就是它本身的值加上右节点的值。可以看到我们中序遍历到最右子节点,先计算节点的右分支,然后计算当前节点,然后再更新左孩子
更多leetcode算法题解法请关注我的专栏或关注我
欢迎大家一起套路一起刷题一起ac
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def bstToGst(self, root: TreeNode) -> TreeNode: new_root=TreeNode(None) sum_num=root.val sum_num+=self.findEqualAndLarge(root.right) new_root.val=sum_num if root.left: tmp1=TreeNode(None) new_root.left=tmp1 self.updateLeftTree(root.left,sum_num,tmp1) if root.right: tmp2=TreeNode(None) new_root.right=tmp2 self.updateRightTree(root.right,sum_num-root.val,tmp2) return new_root def updateLeftTree(self,root,sum_num,new_root): sum_num+=root.val new_root.val=sum_num if root.left==None and root.right==None: return if root.right: new_root.val+=self.findEqualAndLarge(root.right) temp1=TreeNode(None) new_root.right=temp1 self.updateLeftTree(root.right,sum_num-root.val,temp1) if root.left: temp2=TreeNode(None) new_root.left=temp2 self.updateLeftTree(root.left,new_root.val,temp2) def updateRightTree(self,root,sum_num,new_root): new_root.val=sum_num if root.left==None and root.right==None: return if root.left: new_root.val-=self.findEqualAndLarge(root.left) temp1=TreeNode(None) new_root.left=temp1 self.updateRightTree(root.left,sum_num,temp1) if root.right: temp2=TreeNode(None) new_root.right=temp2 self.updateRightTree(root.right,new_root.val-root.val,temp2) def findEqualAndLarge(self,root): sum_num=root.val if root.left==None and root.right==None: return sum_num if root.left: sum_num+=self.findEqualAndLarge(root.left) if root.right: sum_num+=self.findEqualAndLarge(root.right) return sum_num
#version 2n = 0def bstToGst(self, root): """ :type root: TreeNode :rtype: TreeNode """ if root: self.bstToGst(root.right) root.val = self.n = self.n + root.val self.bstToGst(root.left) return root
转载地址:http://mqmrb.baihongyu.com/