只有两种情况：
1. p和q一左一右
2. p或q为另外一个的祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if(root==NULL)  return NULL;   //遇到空返回NULL


        if(root==p || root==q)  return root;    //对应情况2  其中一个就是祖先

        auto left = lowestCommonAncestor( root->left, p, q);     
        auto right = lowestCommonAncestor( root->right, p , q); 

        if(left&&right)  return root;   //对应情况1 如果在root的左右分别找到了p q  那么root即为最近公共祖先

        if(left) return left;   //都在左边返回左边
        else return right;      //都在右边返回右边

    }
};

存储路径

class Solution {
public:

    vector<TreeNode*> find(TreeNode*root, TreeNode*p )
    {
        vector<TreeNode*> s;   //存路径
        TreeNode* t=root, *pre=NULL;

        while(t || s.size() )   //类似后续非递归的修改
        {
            while(t)            //先把左侧全部入栈,
            {
                s.push_back(t);
                t=t->left;
            }         

            t = s.back();        //从最后一个开始操作

            if(t->right&& t->right!=pre)   //右节点存在且没有输出 下一次把他入栈
                t=t->right;                     

            else 
            {
                 if(t == p)  return s;      

                 s.pop_back();
                 pre = t;
                 t = NULL;
            }
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
      vector<TreeNode*> path1 = find(root, p);   //存下来从root到p的路径
      vector<TreeNode*> path2 = find(root, q);

      if( path1.size()>path2.size() ) swap( path1, path2 );

      for(int i=0; i<path1.size(); i++)
      {
          if(path1[i]!=path2[i]) return path1[i-1];
      }

      return path1.back();

    }
};

转化为数组存储