继续刷题，感觉刷题还有乐趣的，搞得都不想去研究量化策略了。如果以前读书时候有这样刷题网站，简单而方便思考实现，估计我的计算机分数会好很多。
题目是在给出二叉树中两个点p，q，求出其最小共同父节点（LCA Lowest Common Ancestor)，如下图很好理解，比如5和1的共同父节点是3；6和7的最小共同父节点是5；而5和4的最小共同父节点是5本身。
考虑了一下，其实思路很简答，首先用前序或者层级遍历二叉树得出节点队列，因为前序和层级都是先遍历父节点再子节点，这样队列后的节点的父节点一定存在队列中。然后从后往前反序遍历这个节点队列，如果是给出p, q这两个中的父节点，则替换为其父节点，如果p和q是同一个节点，就是其最小共同父节点。
代码如下，使用层级遍历，遍历的时候判断是否已经读取p,q；如果都读取了停止遍历，避免读取不必要数据。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:
def lowestCommonAncestor(self, root: ‘TreeNode‘, p: ‘TreeNode‘, q: ‘TreeNode‘) -> ‘TreeNode‘:
preNodeList = []
checkList = [root]
count = 2 while count > 0:
nextList = []
for node in checkList:
preNodeList.append(node)
if node == p or node == q:
count = count -1
if count == 0:
pass
if node.left != None:
nextList.append(node.left)
if node.right != None:
nextList.append(node.right)
checkList = nextList
while p!= q:
currentNode = preNodeList.pop()
if currentNode.right == p or currentNode.left == p:
p = currentNode
if currentNode.right == q or currentNode.left == q:
q = currentNode
return p
|