二叉搜索树的最近公共祖先：最直观的想法是，二叉搜索树的特点是左子树数值<中间节点数值<右子树数值，那么我们可以根据这一特性来遍历二叉搜索树，分别得到从根节点到节点p的路径数组pathp以及从根节点到节点q的路径数组pathq，然后遍历两个数组得到最后一个相同的节点值，其即为二叉搜索树的最近公共祖先。遍历路径具体实现方法如下：首先将当前值加入路径数组，然后比较当前值和目标值，如果当前值大于目标值，则在当前节点的左子树寻找目标值，反之如果当前值小于目标值，则在当前节点的右子树寻找目标值，当找到当前目标值即返回，注意，是先加入再返回这样的顺序喔！

vector<int> pathp;
vector<int> pathq;
// 二叉搜索树：左<中<右
void traverse(TreeNode* cur, int target, vector<int>& path)
{
    // 加入到数组
    path.push_back(cur->val);
    // 找到目标值
    if(cur->val==target)
       return;
    // 当前小于目标则在右子树
    if(cur->val<target)
       traverse(cur->right, target,path);
    // 当前大于目标则在左子树
    else if(cur->val>target)
       traverse(cur->left,target,path);
}
int lowestCommonAncestor(TreeNode* root, int p, int q) 
{
    // 记录结果
    int res;
    // 找到从根节点到p的路径
    traverse(root, p, pathp);
    // 找到从根节点到q的路径
    traverse(root, q, pathq);
    // 找到最后一个相同的节点值
    for(int i=0,j=0;i<pathp.size()&&j<pathq.size();i++,j++)
    {
       if(pathp[i]==pathq[j])
         res=pathp[i];
    }
    return res;
}

优化：既然我们知道二叉搜索树的特性是左子树数值<中间节点数值<右子树数值，那么两个节点假设p<q，则p和q的最近公共祖先一定在区间[p,q]中。上述我们遍历了两次二叉树，其实我们可以优化为只遍历一次二叉树。lowestCommonAncestor函数指的是在以root为根的二叉搜索树中遍历p和q的最近公共祖先，其可以分为如下几种情况：一是如果当前节点值比p和q均大则遍历当前节点的左子树，在以左子树为根的二叉搜索树中遍历p和q的最近公共祖先；二是如果当前节点值比p和q均小则遍历当前节点的右子树，在以右子树为根的二叉搜索树中遍历p和q的最近公共祖先；反之则最近公共祖先即为当前节点值，注意，由于该函数包含返回值，故一旦返回值有值则直接返回。

// 在以root为根的二叉搜索树中遍历p和q的最近公共祖先
int lowestCommonAncestor(TreeNode* root, int p, int q) 
{
    // 题目中说了树不为空 节点值唯一 故这里可以不处理边界条件
    // 记录结果 节点值在0~10000之间 
    int left=-1,right=-1;
    // 当前节点值比p和q均大则遍历当前节点的左子树
    if(root->val>p&&root->val>q)
    {
        left=lowestCommonAncestor(root->left, p, q);
        if(left!=-1)
        return left;
    }    
    // 当前节点值比p和q均小则遍历当前节点的右子树
    if(root->val<p&&root->val<q)
    {
        right=lowestCommonAncestor(root->right, p, q);
        if(right!=-1)
        return right;
    }
    // 否则当前节点值在两者之间返回当前值 其包含p是q祖先或者q是p祖先的情况 就可以减少判断
    return root->val;
}