题目链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
难度：中等

描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

提示：
p，q必在二叉树中且p != q

题解

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
  10.         # 递归终止条件
  11.         if root is None:
  12.             return None
  13.         if p == root or q == root:
  14.             return root
  16.         left = self.lowestCommonAncestor(root.left, p, q)
  17.         right = self.lowestCommonAncestor(root.right, p, q)
  19.         # 没有找到p, q
  20.         if left is None and right is None:
  21.             return None
  22.         # p, q都在右子树中
  23.         if left is None:
  24.             return right
  25.         # p, q都在左子树中
  26.         if right is None:
  27.             return left
  28.         # p, q分别在左右子树中
  29.         return root