三个月算法进阶--day44

def getPath(root: 'TreeNode', target: 'TreeNode') -'TreeNode':
    path = []
    while root != target:
        path.append(root)
        if root.val > target.val:
            root = root.left
        else:
            root = root.right
    path.append(root)
    return path

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while True:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or 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
        else:
            return right