二叉樹：最近的公共祖先 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;
}