leetcode 剑指 Offer 68 - II. 二叉树的最近公共祖先python

leetcode 剑指 Offer 68 - II. 二叉树的最近公共祖先python

题目描述：

题解：

与剑指 Offer 68 - I. 二叉搜索树的最近公共祖先python_ganggang的博客-CSDN博客差别在于不是二叉搜索树，但思路仍然是判断p q分别位于root左右哪个子树。

1.如果root为空，返回None，如果输入root值与p或者q的节点值相等，则返回root。

2.分别对root的左右子树调用lowestCommonAncestor。

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if root==None:
            return None
        if root.val == p.val or root.val==q.val:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left!=None and right!=None:
            return root
        if left!=None:
            return left
        if right!=None:
            return right
        return None