面试题68：树中两个节点的最低公共祖先

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

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

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

思路：
二叉搜索树的特点：左子树小于根节点小于右子树，所以从根节点开始判断，如果根节点的值小于两个节点的值，说明公共节点在右子树；如果根节点的值大于两个节点的值，说明公共节点在左子树；否则在两者之间，就是第一个公共节点

代码实现：

# 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':
        if not root or not p or not q:
            return None
        #第一个公共祖先的值在p，q之间
        minVal = min(p.val,q.val)
        maxVal = max(p.val,q.val)
        while root:
            if root.val>=minVal and root.val<=maxVal:  #找到第一个祖先
                return root
            elif root.val<minVal:  #公共祖先在右子树
                root = root.right
            else:
                root = root.left

提交结果：

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

思路：
利用递归思想，如果pq都在左子树，返回左子树；
如果pq都在右子树，返回右子树
如果pq一边一个，当前节点就是最近祖先

代码：

# 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':
        if not root or root==p or root==q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left is None:
            return right
        elif right is None:
            return left
        else:
            return root  #说明左右子树各一个，该节点为最近公共节点