心路历程:
这道题可以完全按照二叉树的公共祖先来做,但是由于题目中给了二分搜索树的条件,因此可以通过值的大小简化左右子树的递归搜索。
解法一:按照二分搜索树的性质
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
if not node or node == p or node == q: return node
if node.val > p.val and node.val > q.val: return dfs(node.left)
elif node.val < p.val and node.val < q.val: return dfs(node.right)
else: return node
return dfs(root)
解法二:依然用后序遍历搜索
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
if not node or node == p or node == q: return node
lv = dfs(node.left)
rv = dfs(node.right)
if lv and rv: return node
elif lv and not rv: return lv
elif not lv and rv: return rv
else: return None
return dfs(root)