1038. Binary Search Tree to Greater Sum Tree
Problem 1038
https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
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:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
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]Solution
數字會從最大（right）的開始處理，將每一次的 node 數值紀錄並且累加，就會是接下來的 node 所應該加上去的數字。
class Solution(object):
ListNode = []
def bstToGst(self, root):
self.ListNode = []
self.dfs( root )
SumNum = 0
for node in self.ListNode:
SumNum += node.val
node.val = SumNum
return root
def dfs(self, node):
if node:
if node.right:
self.dfs( node.right )
self.ListNode.append( node )
if node.left:
self.dfs( node.left )class SolutionII(object):
def bstToGst(self, root):
self.bstToGst2( root, 0 )
return root
def bstToGst2( self, root, SumNum ):
if root.right:
SumNum = self.bstToGst2( root.right, SumNum )
root.val += SumNum
SumNum = root.val
if root.left:
SumNum = self.bstToGst2( root.left, SumNum )
return SumNumclass SolutionIII(object):
val = 0
def bstToGst(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root.right:
self.bstToGst( root.right )
root.val += self.val
self.val = root.val
if root.left:
self.bstToGst(root.left)
return rootLast updated