Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Discussion

还是LCA问题，只是对BST。对比LCA I问题中通过1）bottom-up approach，在左右子树中分别找LCA，判断两个node是在left subtree or right subtree， 或者左右分别一个；2）Top-Down Approach，通过count左右子树中match nodes的个数来判断是在左右子树中的哪个。如果是BST的话，这些判断就变得非常非常简单了，都比root->val大，那就在右子树，都比它小，就在左子树。不然的话就是一个大一个小，或者有相等的，那就是root了。

Solution

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;
        if(max(p->val, q->val) < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if(min(p->val, q->val) > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else {
            return root;
        }
    }
};

The run time complexity is O(h).

Transfer the tail recursion to iterative method.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;
        stack<TreeNode*> stk;
        stk.push(root);
        int max_v = max(p->val, q->val);
        int min_v = min(p->val, q->val);

        while(stk.empty() == false) {
            TreeNode *cur = stk.top();
            if(max_v < cur->val) {
                stk.push(cur->left);
            } else if(min_v > cur->val) {
                stk.push(cur->right);
            } else {
                return cur;
            }
        }
        return NULL;
    }
};