Tag: BST

Categories
不学无术

LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路

基本思路是，假设当前运行到nums[i]的位置，则需要往前看k个数，并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题（问题就转变为：找到第一个>=nums[i]-t的数，判断他是否<=nums[i]+t）。整个算法的时间复杂度是O(N * logk)，N为数组长度。
下面代码中用set实现，set是用红黑树实现的。

代码

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.empty() || k<1 || t<0)
            return false;
        k++;
        set<int> kNumSet;
        for (int i=0; i<nums.size(); i++){
            if(i >= k){
                int oldVal = nums[i-k];
                kNumSet.erase(oldVal);
            }
            auto l_bound = kNumSet.lower_bound(nums[i] - t);
            if(l_bound != kNumSet.end()){
                if(*l_bound - t <= nums[i])
                    return true;
            }
            kNumSet.insert(nums[i]);
        }
        return false;
    }
};

 

Categories
木有技术

LeetCode 173. Binary Search Tree Iterator

思路

画一个简单的BST，然后可以看出有三种情况

  • 如果当前节点有右孩子，那就在右子树里找到值最小的那个，显然是右子树里最左下侧的那个节点
  • 如果当前节点没有右孩子，由于左子树的值肯定都比当前节点的值小，左右要找父节点
    • 如果找到某个父节点的值比当前节点值大，那这个父节点就是下一节点
    • 否则，当前节点就是最后一个节点

因此，需要一个栈结构记录当前节点的父亲们（有点像调用栈）。
测试例：NULL根节点，只有一个节点，只有单侧树

代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> callStack;
    TreeNode* currNode;
    TreeNode* rootNode;
public:
    BSTIterator(TreeNode *root) {
        currNode = NULL;
        rootNode = root;
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(currNode == NULL){
            currNode = rootNode;
            while(currNode!=NULL && currNode->left != NULL){
                callStack.push(currNode);
                currNode = currNode->left;
            }
            return currNode!=NULL;
        }
        if(currNode->right != NULL){
            //left-most node in right sub-tree
            callStack.push(currNode);
            currNode = currNode->right;
            while(currNode->left != NULL){
                callStack.push(currNode);
                currNode = currNode->left;
            }
            return true;
        } else {
            //look for first parent whos val is > currNode->val. If not available, return false
            int currVal = currNode->val;
            while(!callStack.empty()){
                TreeNode* parent = callStack.top();
                callStack.pop();
                if(parent->val > currVal){
                    currNode = parent;
                    return true;
                }
            }
            currNode = NULL;
            return false;
        }
    }
    /** @return the next smallest number */
    int next() {
        if(currNode != NULL)
            return currNode->val;
        return INT_MIN;
    }
};
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

 

Categories
木有技术

LeetCode 102. Binary Tree Level Order Traversal

练手水题，直接贴代码。快转正面试了，虚啊，鬼晓得BOSS会问点什么。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if(root == NULL)
            return results;
        queue<TreeNode*>* currQueue = new queue<TreeNode*>();
        queue<TreeNode*>* candidateQueue = new queue<TreeNode*>();
        currQueue->push(root);
        vector<int> levelResult;
        while(!currQueue->empty()){
            TreeNode* currNode = currQueue->front();
            currQueue->pop();
            levelResult.push_back(currNode->val);
            if(currNode->left != NULL)
                candidateQueue->push(currNode->left);
            if(currNode->right != NULL)
                candidateQueue->push(currNode->right);
            if(currQueue->empty()){
                //swap curr and candidte
                results.push_back(levelResult);
                levelResult.clear();
                queue<TreeNode*>* temp = currQueue;
                currQueue = candidateQueue;
                candidateQueue = temp;
            }
        }
        return results;
    }
};