Search Range in Binary Search Tree

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

http://www.lintcode.com/en/problem/search-range-in-binary-search-tree/

Discussion

方法一：递归。如果root比k1大，到左子树查找保存下来；然后看要不要保存根； 然后如果root比k2小，到右子树查找保存下来。

方法二：方法一里左中右好眼熟有没有？不就是中序遍历嘛！BST中序遍历的结果就是ascending的，所以只要在其中找range即可，稍微修改中序遍历，只在落入[K1,K2]范围的时候输出。

Solution

Recursion.

class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        // write your code here
        vector<int> result;
        if(root == NULL)
            return result;
        vector<int> l;
        vector<int> r;
        if(k1< root->val)
            l = searchRange(root->left, k1, k2);
        if(k2 > root->val)
            r = searchRange(root->right, k1, k2);
        result.insert(result.end(), l.begin(), l.end());
        if(k1<= root->val&& k2 >= root->val)
            result.push_back(root->val);
        result.insert(result.end(), r.begin(), r.end());
        return result;
    }
};

Iteration

vector<int> searchRange(TreeNode* root, int k1, int k2) {
        // write your code here
        vector<int> result;
        if(root == NULL) {
            return result;
        }
        stack<TreeNode*> stk;
        TreeNode *cur = root;
        while(stk.empty() == false || cur != NULL) {
            if(cur != NULL) {
                stk.push(cur);
                cur = cur->left;
            } else {
                cur = stk.top();
                stk.pop();
                if(cur->val >= k1 && cur->val <= k2) {
                    result.push_back(cur->val);
                }
                cur = cur->right;
            }
        }
        return result;
    }