211. Add and Search Word - Data structure design

https://leetcode.com/problems/add-and-search-word-data-structure-design/

Solution:
May use the prefix trie data structure. Then need DSF for the word searching. As long as there is one path is right, return true; otherwise, return false.

Code:

class WordDictionary {
public:
    struct TrieNode{
        bool end;
        vector<TrieNode*> children;
        TrieNode(): end(false), children(26, NULL) {}
    };
    
    WordDictionary(){//constructor;
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *t = root;
        for(auto a:word){
            if(!t->children[a-'a']) t->children[a-'a'] = new TrieNode();
            t = t->children[a-'a'];
        }
        t->end = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return swDSF(word, root, 0);
    }
    
    bool swDSF(string w, TrieNode* r, int i){
        if(i == w.size()) return r->end;
        if(w[i] == '.'){
             for(auto a:r->children){
                if(a && swDSF(w, a, i+1)) return true;
            }
            return false;
        }
        return r->children[w[i]-'a'] && swDSF(w, r->children[w[i]-'a'], i+1);
    }
    
private:
    TrieNode *root;
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

Solution:
Take a while to figure out what this question is for... (Originally thought it is for the "second" smallest element in the Tree...) OK, here it is. It will always find the next smallest element in the BST if it exists. So if it is called from the beginning until the end, the sequence output will be the elements sorted from mid-order traversal (left -> root -> right) of BST.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *r = root;
        while(r){
            s.push(r);
            r = r->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *t = s.top();
        int res = t->val;
        s.pop();
        if(t->right){
            t = t->right;
            while(t){
                s.push(t);
                t = t->left;
            }
        }
        return res;
    }
private:
    stack<TreeNode*> s;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

http://www.cnblogs.com/grandyang/p/4231455.html