二叉搜索树的最近祖先（递归遍历）

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祖先的情况。则要将递归遍历到的值返回给上一层。最后如果找到中间值点，则将遍历到的节点返回给上一层。