题解 | #在二叉树中找到两个节点的最近公共祖先#

解答本题最关键的核心就是：找到这两个节点路径的公共交点

我们在遍历树的时候，会有很多条从根节点到叶子节点的遍历路径，但里面只可能有两条是经过这两个节点的，且这两条路径必会有相交的一段（除非测试时给出的两个节点中有不属于这棵树的，否则最差的情况就是只有根节点那一块是相交的）。为此，我们可以利用数组将两条路径（根节点->目标节点）分别存起来，然后比对相同的路径段，最后再找出最近的公共交点。

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
      // write code here
      vector<int> v;
      vector<vector<int>> vv;
      FindNode(root, o1, o2, v, vv);
      
      // 找出两条线路的公共交点，该节点即为最近公共祖先
      int temp = -1;
      int len = vv[0].size()>vv[1].size() ? vv[1].size() : vv[0].size();
      for(int i=0; i<len; i++){
        if (vv[0][i]==vv[1][i] && vv[0][i+1]!=vv[1][i+1]){
          temp = i;
          break;
        }
      }
      // 两个节点中有不属于这棵树即没有公共节点，返回-1
      if (temp == -1) { return temp; }
      return vv[0][temp];
    }
    
    void FindNode(TreeNode* root, int o1, int o2, vector<int> &v, vector<vector<int>> &vv) {
      // 递归中止条件
      if (!root){ return; }
      
      v.push_back(root->val);
      // 仅有一条是经过要求节点的
      // 故o1和o2最终只有两个vector，即vv[0]->线路o1, vv[1]->线路o2
      if (root->val == o1){ vv.push_back(v); }
      if (root->val == o2){ vv.push_back(v); }
      
      FindNode(root->left, o1, o2, v, vv);
      FindNode(root->right, o1, o2, v, vv);
      // 回溯
      v.pop_back();
    }
};