二叉树：最近的公共祖先 Lowest Common Ancestor of a Binary Tree

已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低(离根最 远)，且v,w两个节点都是u的子孙。

如上二叉树，6和8号节点的公共祖先有4，1；但是最近的公共祖先仅为4

这里我们发现，想要快速获取两个节点的最近的公共祖先节点，首先需要知道两个节点各自从根节点到当前的路径，即：

6号节点的路径为：[1,4,6]

8号节点的路径为：[1,4,5,8]

/*先序遍历查找路径*/
void getPathToNode(Tree *root, Tree *search,  //root根节点，search为当前节点
            std::vector<Tree *> &path, //存储临时路径
            std::vector<Tree *> &result, //存储最终结果
            int &finish) { //是否找到的状态
  if (!root || finish ) { //如果找到或者根节点为空，则返回空
    return;
  }
  path.push_back(root); 
  if (root == search) { //发现当前节点为我们要找的路径
    finish = 1;
    result = path; //将路径列表给予最终的结果
  }
  /*继续后序左右子树的查找*/
  getPathToNode(root -> left, search, path, result, finish);
  getPathToNode(root -> right, search, path, result, finish);
  /*发现没有找到，则将当前节点pop*/
  result.pop_back();
}      

Tree *getPublicNode(Tree *root, Tree *p, Tree *q) {
  if (root == NULL) {
    return NULL;
  }
  std::vector<Tree *> p_path;//p的最终路径
  std::vector<Tree *> q_path;//q节点的最终路径
  std::vector<Tree *> path;//存储临时路径
  int finish = 0;
  getPathToNode(root, p, path, p_path,finish);
  path.clear();
  finish = 0;
  getPathToNode(root, q, path, q_path,finish);
  int path_len = 0;
  if (p_path.size() > q_path.size()) { //需要取一个最短的路径进行后序的遍历
    path_len = q_path.size();
  }else {
    path_len = p_path.size();
  }

  Tree *result;
  for (int i = 0;i < path_len; ++i) { //从开始（根节点）遍历到叶子节点，越靠后的节点越为最近的公共祖先节点
    if (p_path[i] == q_path[i]) {
      result = p_path[i];
    }
  }
  return result;
}