Solution to LeetCode 108 Convert Sorted Array to Binary Search Tree and LeetCode 538 Convert BST to Greater Tree.
A binary search tree is a tree that satisfies these constraints:
1 The left subtree of a node contains only nodes with keys less than the node’s key.
2 The right subtree of a node contains only nodes with keys greater than the node’s key.
3 Both the left and right subtrees must also be binary search trees.
LeetCode 108
Convert Sorted Array to Binary Search Tree (Easy) [link]
Recursive solution. Find separate point and construct left child and right child recursively.
# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
root = self.construct(nums, 0, len(nums)-1)
return root
def construct(self, nums, left, right):
if left > right:
return None
mid = left + (right-left)//2
mid_root = TreeNode(nums[mid])
mid_root.left = self.construct(nums, left, mid-1)
mid_root.right = self.construct(nums, mid+1, right)
return mid_root
LeetCode 538
Convert BST to Greater Tree (Medium) [link]
If it is an array, the idea is to do cumulative summation from the end to the start. When it comes to a tree, we need reversed inorder traversal.
# 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 __init__(self):
self.pre = TreeNode()
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.traversal(root)
return root
def traversal(self, root):
if not root:
return None
self.traversal(root.right)
root.val += self.pre.val
self.pre = root
self.traversal(root.left)
