求兩個(gè)節(jié)點(diǎn)最近的祖先節(jié)點(diǎn)，思路是找到根節(jié)點(diǎn)到所求節(jié)點(diǎn)的路徑，那么兩條路徑分叉處就是祖先節(jié)點(diǎn)
遞歸，假定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)
# 左子樹返回時(shí)蚓聘，將左子樹拋出
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說明終止循環(huán)是因?yàn)橛胁煌窂?''
else:
return self.pathP[i-1]
