【LeetCode 44】235.二叉搜索树的最近公共祖先

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);
    }
};