- Convert BST to Greater Tree
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
my thoughts:
1. in a BST node.right >= node >= node.left
find the rightmost leaf, inorder travesal (r-n-l) ->
keep track of the sum (need to be independent to the recursion) ->
update node.val with node.val+sum
return root
O(n)
2. iteration.
I want the last in stack to be the rightmost node.
n -> stack
then n.right -> stack
process stack.pop += sum
while n.left, n -> stack
then process stack
my solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.sum = 0
def dfs(n):
if not n:
return
r = dfs(n.right)
n.val = self.sum + n.val
self.sum = n.val
l = dfs(n.left)
dfs(root)
return root
*********************
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return root
a = root
temp = 0
stack = []
while a or stack:
while a:
stack.append(a)
a = a.right
a = stack.pop()
temp = temp + a.val
a.val = temp
a = a.left
return root
my comments: solution accepted, 119ms, 119ms run time from other ppl's solution:
- still needed some help with the iteration. I wans't 100% sure about the a=a.left