2020-10-06

JiayangWu · JiayangWu · commit 016288bc703d · 2020-10-06T23:39:45.000-04:00
diff --git a/剑指Offer68-II.二叉树的最近公共祖先/剑指Offer68-II-二叉树的最近公共祖先.py b/剑指Offer68-II.二叉树的最近公共祖先/剑指Offer68-II-二叉树的最近公共祖先.py
@@ -0,0 +1,29 @@
+# Definition for a binary tree node.
+# class TreeNode(object):
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution(object):
+    def lowestCommonAncestor(self, root, p, q):
+        """
+        :type root: TreeNode
+        :type p: TreeNode
+        :type q: TreeNode
+        :rtype: TreeNode
+        """
+        if not root:
+            return None 
+        if root == p or root == q:
+            return root
+        left = self.lowestCommonAncestor(root.left, p, q)
+        right = self.lowestCommonAncestor(root.right, p, q)
+
+        if left and right:
+            return root
+        if left:
+            return left
+        if right:
+            return right 
+        return None
