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

在二叉树中找到两个节点的最近公共祖先：最直观的想法是，数组存储法。首先遍历二叉树，分别找到从根节点到o1与从根节点到o2的路径数组，然后比较两个数组找到最后一个相同的元素即为o1和o2的最近公共祖先。在遍历二叉树的过程中，由于要找的是从根节点到某一节点的路径，故使用前序遍历。其与二叉搜索树的区别是，二叉搜索树的前序遍历的左和右部分都是满足条件再进入循环，而该普通二叉树中没有，故左边返回后可能还会进入右边，这时我们就需要加一个标记是否找到的全局变量flag，在递归终止条件中需要加上当找到即flag为true时则返回，在左右递归遍历结束后还需要判断flag是否为true，如果是则表明找到返回即可，否则表示没找到则要将当前元素弹出数组。

vector<int> path1;
vector<int> path2;
bool flag=false; // 标记是否找到
// 求解路径数组 
void dfs(TreeNode* root,int o,vector<int>& path)
{
   if(flag||!root) return;  // 当为空或者已经找到则返回空
   path.push_back(root->val);
   if(root->val==o)
   {
       flag=true; // 标记找到 否则后续会继续遍历
       return;
   }
   dfs(root->left,o,path);
   dfs(root->right,o,path);
   // 找到
   if(flag)
     return;
   // 没找到弹出元素
   path.pop_back();
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) 
{
    dfs(root,o1,path1);
    flag=false; // 重置为空
    dfs(root,o2,path2);
    int res;
    // 记录最后一个相同的
    for(int i=0,j=0;i<path1.size()&&j<path2.size();i++,j++)
      if(path1[i]==path2[j])
         res=path1[i];
    return res;
}

idea：上述方法是先找到路径，再比较路径，其实可以边遍历边比较。如果节点为空则返回-1，如果当前节点是两者其中之一，则返回当前节点值，然后再依次遍历左子树和右子树，当左子树返回-1则表明在左子树没找到故返回右子树，反之当右子树返回-1则表明在右子树没找到故返回左子树，反之两个都找到了则表明最近公共祖先即为当前节点。

int lowestCommonAncestor(TreeNode* root, int o1, int o2) 
{
   // 该子树没找到返回-1
   if(root==NULL)
      return -1;
   // 该节点是其中某一个节点
   if(root->val==o1||root->val==o2)
      return root->val;
   // 左子树寻找祖先
   int left=lowestCommonAncestor(root->left, o1, o2);
   // 右子树寻找祖先
   int right=lowestCommonAncestor(root->right, o1, o2);
   // 左子树没找到则在右子树上
   if(left==-1)
      return right;
   // 右子树没找到则在左子树上
   if(right==-1)
      return left;
   // 否则是当前节点
   return root->val;
}