diff options
-rwxr-xr-x | 235/main.py | 57 |
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() |