【Leetcode】235. Lowest Common Ancestor of a Binary Search Tree 解题报告

求二叉排序中的最近公共祖先

方法1 递归法

找到一个节点的值大于左变小于右边即可

class Solution1(object):
    def lowestCommonAncestor(self, root, p, q):
        p = p.val
        q = q.val
        if q < p:
            q,p = p,q
        return  self.find(root, p, q)
    def find(self, root, p, q):
        if root == None:
            return None
        if root.val >=p and root.val <= q:
            return root
        else:
            if root.val > q:
                return self.find(root.left, p, q)
            if root.val < p:
                return self.find(root.right, p, q)

方法2

递归转非递归使用栈

class Solution2(object):
    def lowestCommonAncestor(self, root, p, q):
        p , q = p.val, q.val
        if p > q:
            p,q = q,p
        if root == None:
            return None
        stack = [root]
        while(len(stack)):
            node = stack.pop()
            if node.val >= p and node.val <= q:
                return node
            else:
                if node.val > q:
                    stack.append(node.left)
                if node.val < p:
                    stack.append(node.right)
        return None

方法3

不使用栈的递归，直接用指针遍历即可

class Solution3(object):
    def lowestCommonAncestor(self, root, p, q):
        p, q = p.val, q.val
        if p > q:
            p, q = q, p
        if root == None:
            return None
        pNode = root
        while(pNode):
            if pNode.val >= p and pNode.val <= q:
                return pNode
            else:
                if pNode.val > q:
                    pNode = pNode.left
                else:
                    pNode = pNode.right
        return None