235. 二叉搜索樹的最近公共祖先 - 力扣（LeetCode）
class Solution {
private:TreeNode*traversal(TreeNode*cur,TreeNode*p,TreeNode*q){if(cur==NULL){return NULL;}if(cur->val>p->val&&cur->val>q->val){TreeNode*left=traversal(cur->left,p,q);if(left!=NULL){return left;}}if(cur->val<p->val&&cur->val<q->val){TreeNode*right=traversal(cur->right,p,q);if(right!=NULL){return right;}}return cur;};
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};終止條件：在遍歷到最后時，如果還沒有找到目標節點，到達空節點，則將空返回給上一層遞歸。
單層遞歸邏輯：要想找到最近祖先，就是去找第一次到達q與p中間值的節點。由于二叉搜索樹的特性，如果遍歷到的節點值大于q與p，則向左面遍歷；如果遍歷到的節點值小于q與p，則向右面遍歷。如果直接向下遍歷，則會一直遍歷左右子樹的，遍歷到的節點錯過成為q與p祖先的情況。則要將遞歸遍歷到的值返回給上一層。最后如果找到中間值點，則將遍歷到的節點返回給上一層。
