```# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param p int整型
# @param q int整型
# @return int整型
#
"""
若为二叉搜索树
class Solution:
def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
while True:
if root.val<min(p,q):
root=root.right
elif root.val>max(p,q):
root=root.left
else:
return root.val
"""
"""
一般二叉树
"""
class Solution:
def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
return self.CommonAncestor(root, p, q).val
def CommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
if root==None:
return None
if root.val==p or root.val==q:
return root
left= self.CommonAncestor(root.left, p, q)
right=self.CommonAncestor(root.right, p, q)
if left==None:
return right
elif right==None:
return left
else:
return root
##### 二叉搜索树:若p、q和root.val比较递归
一般二叉树:root左儿子包含p、q中的一个,右二字包含p、q中的另一个,return root,
若p、q都在root左二子中,则root=root.left.若p、q都在root右二子中,则root=root.right.