https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

lowest-common-ancestor-of-a-binary-tree.py

# 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
        """
        def get_path(path, root, node):
            if root is None: return None
            path.append(root)
            if node == root: return path
            if root.left:
                left_path = get_path(path, root.left, node)
                if left_path: return left_path
            if root.right:
                right_path = get_path(path, root.right, node)
                if right_path: return right_path
            path.pop()
            return None
            
        p_path = get_path([], root, p)
        q_path = get_path([], root, q)        
        short_path = min(len(p_path), len(q_path))        
        LCA = None
        for i in range(short_path):
            if p_path[i] == q_path[i]:
                LCA = p_path[i]
        return LCA