aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rwxr-xr-x235/main.py57
1 files changed, 57 insertions, 0 deletions
diff --git a/235/main.py b/235/main.py
new file mode 100755
index 0000000..29b186d
--- /dev/null
+++ b/235/main.py
@@ -0,0 +1,57 @@
+#!/usr/bin/env python3
+
+# 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 root is None:
+ return None
+
+ cur = root
+
+ while cur:
+ if cur.val > p.val and cur.val > q.val:
+ cur = cur.left
+ elif cur.val < p.val and cur.val < q.val:
+ cur = cur.right
+ else:
+ return cur
+
+
+def main():
+ node11 = TreeNode(6)
+ node12 = TreeNode(2)
+ node13 = TreeNode(8)
+ node14 = TreeNode(0)
+ node15 = TreeNode(4)
+ node16 = TreeNode(7)
+ node17 = TreeNode(9)
+ node18 = TreeNode(3)
+ node19 = TreeNode(5)
+
+ node11.left = node12
+ node11.right = node13
+ node12.left = node14
+ node12.right = node15
+ node13.left = node16
+ node13.right = node17
+ node15.left = node18
+ node15.right = node19
+
+ solution = Solution()
+ print(solution.lowestCommonAncestor(node11, node12, node15).val)
+ print(solution.lowestCommonAncestor(node11, node17, node19).val)
+ print(solution.lowestCommonAncestor(node11, node19, node17).val)
+ print(solution.lowestCommonAncestor(node11, node19, node14).val)
+
+
+if __name__ == "__main__":
+ main()