# 236. Lowest Common Ancestor of a Binary Tree

```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]   ```

0 条评论

## 相关文章

14610

8510

11150

10520

### 数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识，C 表示孩子结点标识，L/R...

32030

### 03-树2. List Leaves (25) 二叉树的层序遍历

03-树2. List Leaves (25) 题目来源：http://www.patest.cn/contests/mooc-ds/03-%E6%A0%912...

27590

27750

32660

20250

15810