Leetcode 236 python

解题思路：二叉树节点最低公共祖先，可转化为两链条的最后一个公共节点。难点为如何找到两个节点的路径。

# 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 findPath(self, root, node, path):
        if root == node:
            return True
        if root.left is not None:
            path.append(root.left)
            if self.findPath(root.left,node,path):
                return True
            else:
                path.pop()
        if root.right is not None:
            path.append(root.right)
            if self.findPath(root.right,node,path):
                return True
            path.pop()
        return False

    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return root
        if p is None:
            return q
        if q is None:
            return p
        if p == root or q == root:
            return root
        path_p = [root]
        path_q = [root]
        self.findPath(root,p,path_p)
        self.findPath(root,q,path_q)
        i = 0
        while(i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]):
            ans = path_p[i]
            i += 1
        return ans