題目

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

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

例如，給定如下二叉搜索樹: 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
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。
示例 2:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

思路

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

代碼

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