题目描述：给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。【注】假设给出的两个节点都在树中存在。

## Solutions

涉及到树的操作一般都联想到递归，而树都是从根节点开始遍历的。

• 如果遍历到当前结点，左子树和右子树的遍历结果都有值，说明当前结点就是要找的最近公共父节点；
• 如果左右子树的遍历结果只有一个有值，说明最近公共父节点在那个有值的子树中。
• 递归出口有很多需要注意。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""

class Solution:
"""
@param: root: The root of the binary search tree.
@param: A: A TreeNode in a Binary.
@param: B: A TreeNode in a Binary.
@return: Return the least common ancestor(LCA) of the two nodes.
"""
def lowestCommonAncestor(self, root, A, B):
# write your code here
if root is None or root == A or root == B:
return root
left = self.lowestCommonAncestor(root.left, A, B)
right = self.lowestCommonAncestor(root.right, A, B)

if left is not None and right is not None:
return root

if left is not None:
return left

if right is not None:
return right

return None


LeetCode 上有将结果精简到 4 行的操作，很厉害：

def lowestCommonAncestor(self, root, p, q):
if root in (None, p, q): return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
return root if left and right else left or right