若图片出锅请转至here

概念

首先是最近公共先人的概念(甚么是最近公共先人？)：

在一棵没有环的树上，每一个节点肯定有其父亲节点和先人节点，而最近公共先人，就是两个节点在这棵树上深度最大的公共的先人节点。在一棵没有环的