235. Lowest Common Ancestor of a Binary Search Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*Acception of mine 二叉排序树*/
/*
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s;
        if (!p || !q) return NULL;
        TreeNode* r;
        r = root;
        // push all the path of the p
        while(r && p && r->val != p->val)
        {
            if(r->val>p->val) {s.push(r);r = r->left;}           
            else if(r->val<p->val) {s.push(r);r= r->right;}        
            else break;
        }
        s.push(r);      
        // from the path ,get one node,seach if this node is the parent of q,if yes ,return .
        while(!s.empty())
        {
            TreeNode* ans = s.top(); s.pop();
            r = ans;
            while(r && q)
            {
                if(q->val > r->val) r = r->right;               
                else if(q->val == r->val) return ans;
                else r= r->left;                
            }
        }
        if(s.empty()) return NULL;
    }
};
*/
/*
wonderful Acception!
Just walk down from the whole tree’s root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root’s). This walks straight from the root to the LCA, not looking at the rest of the tree, so it’s pretty much as fast as it gets. A few ways to do it:
*/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while((root->val-p->val) * (root->val - q->val)>0){
            root = p->val < root->val ? root->left:root->right; 
        }
        return root;
};
};