236. Lowest Common Ancestor of a

求两个节点最近的祖先节点，思路是找到根节点到所求节点的路径，那么两条路径分叉处就是祖先节点
递归，假定root不是p,也是不是q,不然root就为所求

class Solution(object): 
    def findpq(self, root, p, q):
        if not root or(self.pathP and self.pathQ):
            return 
        if root == p:
            self.pathP = self.mycopy(self.path)
            
        if root == q:
            self.pathQ = self.mycopy(self.path)
        if root.left:
            # 将左子树加入路径
            self.path.append(root.left)
            self.findpq(root.left, p, q)
            # 左子树返回时，将左子树抛出
            self.path.pop()
        if root.right:
            self.path.append(root.right)
            self.findpq(root.right, p ,q)
            self.path.pop()    
   def mycopy(self,path):
        pathcopy = []
        for el in path:
            pathcopy.append(el)
        return pathcopy
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root ==p or root == q:
            return root
        self.pathP = None
        self.pathQ = None
        self.path = []
        self.findpq(root, p, q)
        #print self.path
        i = 0
        flag = 0
        minpathLen = min(len(self.pathP), len(self.pathQ))
        for i in range(minpathLen):
            if self.pathP[i] != self.pathQ[i]:
                flag = 1
                break
        # 确定路径长度为i
        if i == 0 and flag==1:
            return root
        #print self.pathP
        if flag == 0:
            return self.pathP[i]
            '''else说明终止循环是因为有不同路径'''
        else:
            return self.pathP[i-1]