255. Verify Preorder Sequence in Binary Search Tree

I was trying divide and conquer solution as following but got TLE.

1:  class Solution {  
2:  public:  
3:    bool verifyPreorder(vector<int>& preorder) {  
4:      if (preorder.empty()) return true;  
5:      return helper(preorder, 0, preorder.size()-1);  
6:    }  
7:    bool helper(vector<int> &preorder, int s, int e) {  
8:      if (s >= e) return true;  
9:      int pivot = preorder[s];  
10:      int bigger = -1;  
11:      for (int i = s+1; i <= e; i++) {  
12:        if (bigger == -1 && preorder[i] > pivot) bigger = i;  
13:        if (bigger != -1 && preorder[i] < pivot) return false;  
14:      }  
15:      if (bigger == -1) {  
16:        return helper(preorder, s+1, e);  
17:      } else {  
18:        return helper(preorder, s+1, bigger-1) && helper(preorder, bigger, e);  
19:      }  
20:    }  
21:  };  

Then I have to follow the top rated solution which uses stack. The idea is to traverse the list and use a stack to store all predecessors. As long as the stack's top node is less than the current list node, we can assume that the current list node is a predecessor and push it to the stack. Once we meet a node that is larger than the top node, we know we are going to enter the right subtree and we need to pop out all the predecessors that are less than current list node but keep the last predecessor. And then we push the current list node into stack and we enters the right subtree. Note for the right subtree, all the node must be larger than the last predecessor, if not then we conclude that it is an invalid preorder sequence in BST.

1:  class Solution {  
2:  public:  
3:    bool verifyPreorder(vector<int>& preorder) {  
4:      if (preorder.size() < 2) return true;  
5:      stack<int> stk;  
6:      stk.push(preorder[0]);  
7:      int last = INT_MIN;  
8:      for (int i = 1; i < preorder.size(); i++) {  
9:        if (stk.empty() || preorder[i] < stk.top()) {  
10:          if (preorder[i] < last) return false;  
11:          stk.push(preorder[i]);  
12:        } else {  
13:          while (!stk.empty() && stk.top() < preorder[i]) {  
14:            last = stk.top();  
15:            stk.pop();  
16:          }  
17:          stk.push(preorder[i]);  
18:        }  
19:      }  
20:      return true;  
21:    }  
22:  };  

144. Binary Tree Preorder Traversal

Not much to say. Pretty straightforward.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<int> preorderTraversal(TreeNode* root) {  
13:      stack<TreeNode *> stk;  
14:      vector<int> res;  
15:      if (root == NULL) return res;  
16:      stk.push(root);  
17:      while (!stk.empty()) {  
18:        TreeNode *t = stk.top();  
19:        stk.pop();  
20:        res.push_back(t->val);  
21:        if (t->right) stk.push(t->right);  
22:        if (t->left) stk.push(t->left);  
23:      }  
24:      return res;  
25:    }  
26:  };  

173. Binary Search Tree Iterator

This is actually a iterative traversal of BST by the help of stack.

1:  /**  
2:   * Definition for binary tree  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class BSTIterator {  
11:  private:  
12:    stack<TreeNode *> stk;  
13:  public:  
14:    BSTIterator(TreeNode *root) {  
15:      while (root) {  
16:        stk.push(root);  
17:        root = root->left;  
18:      }  
19:    }  
20:    /** @return whether we have a next smallest number */  
21:    bool hasNext() {  
22:      return !stk.empty();  
23:    }  
24:    /** @return the next smallest number */  
25:    int next() {  
26:      TreeNode *t = stk.top();  
27:      stk.pop();  
28:      if (t->right) {  
29:        TreeNode *p = t->right;  
30:        while (p) {  
31:          stk.push(p);  
32:          p = p->left;  
33:        }  
34:      }  
35:      return t->val;  
36:    }  
37:  };  
38:  /**  
39:   * Your BSTIterator will be called like this:  
40:   * BSTIterator i = BSTIterator(root);  
41:   * while (i.hasNext()) cout << i.next();  
42:   */  

297. Serialize and Deserialize Binary Tree

The serialization and deserialization can be done by preorder tree traversal. When I revisit the problem, I made a mistake in line 24. Without this line, there'll be "Runtime Error" when input is "null".

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Codec {  
11:  public:  
12:    // Encodes a tree to a single string.  
13:    string serialize(TreeNode* root) {  
14:      if (root == NULL) return "#";  
15:      string s = to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);  
16:      return s;  
17:    }  
18:    // Decodes your encoded data to tree.  
19:    TreeNode* deserialize(string data) {  
20:      return helper(data);  
21:    }  
22:    TreeNode* helper(string &data) {  
23:      if (data[0] == '#') {  
24:        if (data.size() > 1) data = data.substr(2);  
25:        return NULL;  
26:      }  
27:      TreeNode *root = new TreeNode(integer(data));  
28:      root->left = helper(data);  
29:      root->right = helper(data);  
30:      return root;  
31:    }  
32:    int integer(string &data) {  
33:      int i = data.find(',');  
34:      int val = stoi(data.substr(0, i));  
35:      data = data.substr(i+1);  
36:      return val;  
37:    }  
38:  };  
39:  // Your Codec object will be instantiated and called as such:  
40:  // Codec codec;  
41:  // codec.deserialize(codec.serialize(root));  

105. Construct Binary Tree from Preorder and Inorder Traversal

Same idea as "106. Construct Binary Tree from Inorder and Postorder Traversal".

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {  
13:      if (preorder.empty() || preorder.size() != inorder.size()) return NULL;  
14:      return helper (preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);  
15:    }  
16:    TreeNode *helper(vector<int> &preorder, int ps, int pe, vector<int> &inorder, int is, int ie) {  
17:      if (ps > pe || is > ie) return NULL;  
18:      int i = is;  
19:      for (; i <= ie; i++) {  
20:        if (preorder[ps] == inorder[i]) break;  
21:      }  
22:      TreeNode *node = new TreeNode(preorder[ps]);  
23:      node->left = helper(preorder, ps+1, ps+i-is, inorder, is, is+i-1);  
24:      node->right = helper(preorder, ps+i-is+1, pe, inorder, i+1, ie);  
25:      return node;  
26:    }  
27:  };