mq042.二叉树的最近公共祖先

# 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':
        path_p, path_q = list(), list()

        def traversal(node, target, path):
            if not node:
                return False
            path.append(node)
            if node.val == target:
                return True
            if traversal(node.left, target, path) or traversal(node.right, target, path):
                return True
            path.pop()
        
        traversal(root, p.val, path_p)
        traversal(root, q.val, path_q)

        i = 0
        while i < len(path_q) and i < len(path_p) and path_p[i] == path_q[i]:
            res = path_p[i]
            i += 1
        return res