leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

lowest.py (688B)

      1 # Definition for a binary tree node.
      2 # class TreeNode:
      3 #     def __init__(self, x):
      4 #         self.val = x
      5 #         self.left = None
      6 #         self.right = None
      7 
      8 
      9 class Solution:
     10     def lowestCommonAncestor(
     11         self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
     12     ) -> "TreeNode":
     13         if p.val > q.val:
     14             temp = p
     15             p = q
     16             q = temp
     17 
     18         return dfs(root, p, q)
     19 
     20 
     21 # Assume input of p <= q
     22 def dfs(current, p, q):
     23     assert not current is None
     24 
     25     if p.val <= current.val and q.val >= current.val:
     26         return current
     27 
     28     if current.val > p.val:
     29         return dfs(current.left, p, q)
     30     else:
     31         return dfs(current.right, p, q)