求两个节点最近的祖先节点，思路是找到根节点到所求节点的路径，那么两条路径分叉处就是祖先节点
递归，假定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]
