LeetCode Day 21 binary tree (7/9)
Published:
Starting day 7 of practice, binary trees are almost done.
Question 1
530. Minimum Absolute Difference in BST
Given the
rootof a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
The first reaction when I see BST is usually British summer time =_=. Since it is a binary search tree, it is ordered and can be treated as an ordered array.
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
stack = []
cur = root
pre = None
result = float('inf')
while cur is not None or len(stack) > 0:
if cur is not None:
stack.append(cur)
cur = cur.left # Left
else:
cur = stack.pop()
if pre is not None: # Mid
result = min(result, cur.val - pre.val)
pre = cur
cur = cur.right # Right
return result
Question 2
501. Find Mode in Binary Search Tree
Given the
rootof a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
- Both the left and right subtrees must also be binary search trees.
class Solution:
def searchBST(self, cur, freq_map):
if cur is None:
return
freq_map[cur.val] += 1
self.searchBST(cur.left, freq_map)
self.searchBST(cur.right, freq_map)
def findMode(self, root):
freq_map = defaultdict(int) # key: element，value: frequency
result = []
if root is None:
return result
self.searchBST(root, freq_map)
max_freq = max(freq_map.values())
for key, freq in freq_map.items():
if freq == max_freq:
result.append(key)
return result
Question 3
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes
pandqas the lowest node inTthat has bothpandqas descendants (where we allow a node to be a descendant of itself).”
It would be great if we could figure out how to do a bottom-up lookup. Exactly corresponds to the idea of backtracking.
A backward traversal (left to right to middle) is a natural backtracking process that can handle the logic of the middle node based on the return values of the left and right subtrees.
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == q or root == p or root is None:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left is not None and right is not None:
return root
if left is None and right is not None:
return right
elif left is not None and right is None:
return left
else:
return None