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:   */  

114. Flatten Binary Tree to Linked List

My solution is create a helper function that intakes a root and return the last node in the flatten list. So the tree can be flatten by flattening left and right child respectively and move the left child to right and connect the right child to the last node in the left flatten child.

1:  class Solution {  
2:  public:  
3:    void flatten(TreeNode* root) {  
4:      if (root == NULL) return;  
5:      helper(root);  
6:    }  
7:    TreeNode *helper(TreeNode *root) {  
8:      if (root->left == NULL && root->right == NULL) return root;  
9:      TreeNode *left = NULL;  
10:      TreeNode *right = NULL;  
11:      if (root->left != NULL) {  
12:        left = helper(root->left);  
13:        left->right = root->right;  
14:        root->right = root->left;  
15:        root->left = NULL;  
16:        if (left->right != NULL) {  
17:          return helper(left->right);  
18:        } else {  
19:          return left;  
20:        }  
21:      } else {  
22:        return helper(root->right);  
23:      }  
24:    }  
25:  };  

Also, my solution is quite slow (only beats 12%). It can be improved as following:

1:  class Solution {  
2:  public:  
3:    void flatten(TreeNode* root) {  
4:      helper(root);  
5:    }  
6:    TreeNode *helper(TreeNode *root) {  
7:      if (root == NULL) return NULL;  
8:      TreeNode *l_end = helper(root->left);  
9:      TreeNode *r_end = helper(root->right);  
10:      if (l_end) {  
11:        TreeNode *tmp = root->right;  
12:        root->right = root->left;  
13:        root->left = NULL;  
14:        l_end->right = tmp;  
15:      }  
16:      return r_end ? r_end : (l_end ? l_end : root);  
17:    }  
18:  };