原题
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.left = None
6 # self.right = None
7
8 class Solution:
9 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
10 dic = {root:root}
11
12 def dfs(root):
13 if not root:return
14 if root.left:
15 dic[root.left] = root
16 dfs(root.left)
17 if root.right:
18 dic[root.right] = root
19 dfs(root.right)
20
21 dfs(root)
22
23 pl,ql = [p],[q]
24 def helper(node,l):
25 while dic[node] != root:
26 l.append(dic[node])
27 node = dic[node]
28 l.append(root)
29
30 helper(p,pl)
31 helper(q,ql)
32
33 indexpl,indexql,ans = len(pl)-1,len(ql)-1,root
34
35 while indexpl >= 0 and indexql >= 0:
36 if pl[indexpl].val != ql[indexql].val:break
37 ans = pl[indexpl]
38 indexpl -= 1
39 indexql -= 1
40 return ans