一、题意
二、解答过程
与 《二叉树的最近公共祖先》不同，普通二叉树求最近公共祖先需要利用回溯自底向上查找公共节点，而二叉搜索树就不用了，因为二叉搜索树是有序的（相当于自带方向），只要自上而下遍历二叉搜索树即可。
可以采用前序遍历(中-左-右)。
遍历二叉搜索树的过程就是：需找区间[p->val,q->val]；如果cur节点在[p->val,q->val]或者 [q->val,p->val]区间，那么 cur就是最近公共祖先，直接返回 cur。
- 6在0和3的同侧，需要继续左遍历
- 2在0和3的中间，那么2就是最近公共祖先
class Solution { public: //1. TreeNode* traversal(TreeNode *cur,TreeNode *p,TreeNode *q) { //2. if(cur==NULL) return cur; //3. if(cur->val>p->val&&cur->val>q->val)//不断向左遍历左子树 {//p和q在当前节点同侧，需要继续遍历 TreeNode* left=traversal(cur->left,p,q); if(left!=NULL) { return left; } } if(cur->val<p->val&&cur->val<q->val)//不断向右遍历右子树 {//p和q在当前节点同侧，需要继续遍历 TreeNode *right=traversal(cur->right,p,q); if(right!=NULL) { return right; } } return cur; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { return traversal(root,p,q); } };
