原题
给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。
两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。
每个节点除了左右儿子指针以外，还包含一个父亲指针parent，指向自己的父亲。
对于下面的这棵二叉树
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
解题思路
- 根据p，一路向上找到所有的parent，得到一个list
- 根据q，一路向上找到所有的parent，得到一个list
- 从左向右看两个list，最先一样的node即为公共祖先
完整代码
"""
Definition of ParentTreeNode:
class ParentTreeNode:
def __init__(self, val):
this.val = val
this.parent, this.left, this.right = None, None, None
"""
class Solution:
"""
@param root: The root of the tree
@param A and B: Two node in the tree
@return: The lowest common ancestor of A and B
"""
def lowestCommonAncestorII(self, root, p, q):
list = []
while p:
list.append(p)
p = p.parent
while q:
if q in list:
return q
q = q.parent
