亚洲AV永久无码精品久久麻豆 ,天天操天天摸天天日不卡,人妻天天爽夜夜爽,国产高清无码免费视频,亚洲综合777777,91亚洲国产成人久久精,亚洲国产精品久久久,日女人精品视品在线观看

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 二叉搜索樹的最近公共祖先，我們先來看題面：

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

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

示例

示例 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é)點且均存在于給定的二叉搜索樹中。

解題

這題讓求二叉搜索樹的最近公共祖先，而二叉搜索樹的特點就是左子樹的所有節(jié)點都小于當(dāng)前節(jié)點，右子樹的所有節(jié)點都大于當(dāng)前節(jié)點，并且每棵子樹都具有上述特點，所以這題就好辦了，從更節(jié)點開始遍歷

如果兩個節(jié)點值都小于根節(jié)點，說明他們都在根節(jié)點的左子樹上，我們往左子樹上找
如果兩個節(jié)點值都大于根節(jié)點，說明他們都在根節(jié)點的右子樹上，我們往右子樹上找
如果一個節(jié)點值大于根節(jié)點，一個節(jié)點值小于根節(jié)點，說明他們他們一個在根節(jié)點的左子樹上一個在根節(jié)點的右子樹上，那么根節(jié)點就是他們的最近公共祖先節(jié)點。

遞歸法

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        elif root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return root

非遞歸：

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if root.val > max(p.val, q.val):
                root = root.left
            elif root.val < min(p.val, q.val):
                root = root.right
            else:
                return root
        return root