題目

給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）?！?

例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 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, 因為根據定義最近公共祖先節點可以為節點本身。

說明:

所有節點的值都是唯一的。
p、q 為不同節點且均存在于給定的二叉搜索樹中。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路

直接查找
基于二叉搜索樹的特性，直接查找最近的公共祖先。最近公共祖先應該是第一個介于p,q之間的節點（這題p,q大小關系不定），直接搜索就可以了。代碼如下：

代碼

ref：https://leetcode-cn.com/problems/two-sum/solution/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-py/

            
              
                # 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
              
               p
              
                .
              
              val 
              
                >
              
              q
              
                .
              
              val
              
                :
              
              
            p
              
                ,
              
              q 
              
                =
              
              q
              
                ,
              
              p
        
              
                while
              
              
                True
              
              
                :
              
              
                if
              
               root
              
                .
              
              val
              
                >
              
              q
              
                .
              
              val
              
                :
              
              
                root 
              
                =
              
               root
              
                .
              
              left
            
              
                elif
              
               root
              
                .
              
              val 
              
                <
              
               p
              
                .
              
              val
              
                :
              
              
                root 
              
                =
              
               root
              
                .
              
              right
            
              
                else
              
              
                :
              
              
                return
              
               root