題目

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

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

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

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

說(shuō)明:

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

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

思路

直接查找
基于二叉搜索樹(shù)的特性，直接查找最近的公共祖先。最近公共祖先應(yīng)該是第一個(gè)介于p,q之間的節(jié)點(diǎn)（這題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