Knowledge
Lowest common ancestor
Ref
题目
- 98. Validate Binary Search Tree
- 230. Kth Smallest Element in a BST
- 235. Lowest Common Ancestor of a Binary Search Tree
解析
98. Validate Binary Search Tree
- 前序遍历
- 对于root没有任何限制，所以min_limit传一个非常非常小的值，max_limit传一个非常非常大的值
- 如果节点不存在，返回True，因为不存在的节点是一个valid BST
- 对于每一个节点，如果该节点存在，判断 min_limit < root.val < max_limit，如果OK，再去递归判断它的左子树 和 右子树
- 如果不OK，直接返回，因为不是一个valid BST
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(root, min_limit, max_limit):
if not root:
return True
if not (root.val > min_limit and root.val < max_limit):
return False
return dfs(root.left, min_limit, root.val) and dfs(root.right, root.val,
max_limit)
return dfs(root, -1000000000000000000, 100000000000000000)
Ref
Lowest Common Ancestor
235. Lowest Common Ancestor of a Binary Search Tree
- 如果p和q分别在当前节点的左边和右边（即p 比当前节点小，q比当前节点大），当前节点就是 LCA
- 如果p 等于当前节点，则p 和 q的 LCA一定是p
- 如果q 等于当前节点，则p 和 q的 LCA一定是q
- 如果p和q都比当前节点小，则向左下去找LCA
- 因为题目保证p和q都一定存在，所以不需要做额外的判断操作
- 如果p和q都比当前节点大，则向右下去找LCA
- 因为题目保证p和q都一定存在，所以不需要做额外的判断操作
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
n = root
while True:
if p.val < n.val and q.val < n.val:
n = n.left
elif p.val > n.val and q.val > n.val:
n = n.right
else:
return n
Ref
中序遍历 - DFS/BFS - 230. Kth Smallest Element in a BST
- 尽可能的往左下走，直接走不了
- 注意，BFS中中序遍历会将元素从小到大的打印
# DFS
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
found = [False]
res = [-1]
my_k = [k]
def dfs(root):
if not root:
return
if not root.left:
found[0] = True
dfs(root.left)
# current node
if found[0] and my_k[0] == 1:
res[0] = root.val
my_k[0] -= 1
dfs(root.right)
dfs(root)
return res[0]
# BFS
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = [root]
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
n = stack.pop(-1)
if k == 1:
return n.val
k -= 1
cur = n.right
ref