94. Binary Tree Inorder Traversal

The idea is to keep pushing left child nodes into the stack. And pop out the top one, move the pointer to its right and then keep pushing left child nodes again.

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> inorderTraversal(TreeNode* root) {  
13:      stack<TreeNode*> stk;  
14:      TreeNode *p = root;  
15:      vector<int> res;  
16:      while (p || !stk.empty()) {  
17:        while (p) {  
18:          stk.push(p);  
19:          p = p->left;  
20:        }  
21:        p = stk.top();  
22:        stk.pop();  
23:        res.push_back(p->val);  
24:        p = p->right;  
25:      }  
26:      return res;  
27:    }  
28:  };  

257. Binary Tree Paths

This a problem of DFS over tree. The trick here is the termination for DFS should be the node is a leaf node instead of NULL, otherwise, you'll output duplicated path. Also need to be careful about the output format.

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<string> binaryTreePaths(TreeNode* root) {  
13:      vector<string> res;  
14:      if (root == NULL) return res;  
15:      helper(root, "", res);  
16:      return res;  
17:    }  
18:    void helper(TreeNode* root, string path, vector<string> &res) {  
19:      if (root->left == NULL && root->right == NULL) {  
20:        res.push_back(path+to_string(root->val));  
21:        return;  
22:      }  
23:      if (path.empty()) {  
24:        if (root->left) helper(root->left, to_string(root->val)+"->", res);  
25:        if (root->right) helper(root->right, to_string(root->val)+"->", res);  
26:      } else {  
27:        if (root->left) helper(root->left, path+to_string(root->val)+"->", res);  
28:        if (root->right) helper(root->right, path+to_string(root->val)+"->", res);  
29:      }  
30:    }  
31:  };  

272. Closest Binary Search Tree Value II

The O(n) solution will be straight forward. We can output all the nodes into an array, find the position where target is supposed in and move two pointers as predecessor and successor to output the closest k numbers. This also can be done by two stacks.

1:  class Solution {  
2:  public:  
3:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
4:      vector<int> nodes;  
5:      vector<int> res;  
6:      inorder(root, nodes);  
7:      if (nodes.size() == 0) return res;  
8:      int l = 0, r = nodes.size()-1;  
9:      if (target < nodes[l]) {  
10:        while (k--) res.push_back(nodes[l++]);  
11:        return res;  
12:      }  
13:      if (target > nodes[r]) {  
14:        while (k--) res.push_back(nodes[r--]);  
15:        return res;  
16:      }  
17:      while (l <= r) {  
18:        int mid = l + (r - l) / 2;  
19:        if (nodes[mid] == target) {r = mid; break;}  
20:        else if (nodes[mid] > target) r = mid - 1;  
21:        else l = mid+1;  
22:      }  
23:      l = r;  
24:      r = l+1;  
25:      while (k--) {  
26:        if (l < 0) res.push_back(nodes[r++]);  
27:        else if (r == nodes.size()) res.push_back(nodes[l--]);  
28:        else if (abs(nodes[l]-target) < abs(nodes[r]-target)) {  
29:          res.push_back(nodes[l--]);  
30:        } else {  
31:          res.push_back(nodes[r++]);  
32:        }  
33:      }  
34:      return res;  
35:    }  
36:    void inorder(TreeNode *root, vector<int> &nodes) {  
37:      if (root == NULL) return;  
38:      inorder(root->left, nodes);  
39:      nodes.push_back(root->val);  
40:      inorder(root->right, nodes);  
41:    }  
42:  };  

There is another way to maintain the predecessor and successor stack by traversing the tree in inorder and reverse-inorder.

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> closestKValues(TreeNode* root, double target, int k) {  
13:      stack<int> predecessor;  
14:      stack<int> successor;  
15:      inorder(root, false, predecessor, target);  
16:      inorder(root, true, successor, target);  
17:      vector<int> res;  
18:      while (k--) {  
19:        if (predecessor.empty()) {  
20:          res.push_back(successor.top());  
21:          successor.pop();  
22:        } else if (successor.empty()) {  
23:          res.push_back(predecessor.top());  
24:          predecessor.pop();  
25:        } else if (abs(predecessor.top()-target) < abs(successor.top()-target)) {  
26:          res.push_back(predecessor.top());  
27:          predecessor.pop();  
28:        } else {  
29:          res.push_back(successor.top());  
30:          successor.pop();  
31:        }  
32:      }  
33:      return res;  
34:    }  
35:    void inorder(TreeNode *root, bool reverse, stack<int> &stk, double target) {  
36:      if (root == NULL) return;  
37:      inorder(reverse ? root->right : root->left, reverse, stk, target);  
38:      if ((reverse && root->val <= target) || ((!reverse) && root->val > target)) return;  
39:      stk.push(root->val);  
40:      inorder(reverse ? root->left : root->right, reverse, stk, target);  
41:    }  
42:  };  

And this problem actually can be converted to a design problem with two methods getPredecessor() and getSuccessor(). We can stop searching the BST when we find the closest predecessor and successor to target. And we can update the predecessor stack and successor stack in these two methods respectively. So the running time will be O(klogn);

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:  private:  
12:    stack<treenode> pred;  
13:    stack<treenode> succ;  
14:  public:  
15:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
16:      vector<int> res;  
17:      initPredecessor(root, target);  
18:      initSuccessor(root, target);  
19:      if (!succ.empty() &amp;&amp; !pred.empty() &amp;&amp; succ.top()-&gt;val == pred.top()-&gt;val) {  
20:        getNextPredecessor();  
21:      }  
22:      while (k--) {  
23:        if (succ.empty()) res.push_back(getNextPredecessor());  
24:        else if (pred.empty()) res.push_back(getNextSuccessor());  
25:        else if (abs(succ.top()->val - target) < abs(pred.top()->val - target)) {  
26:          res.push_back(getNextSuccessor());  
27:        } else {  
28:          res.push_back(getNextPredecessor());  
29:        }  
30:      }  
31:      return res;  
32:    }  
33:    void initPredecessor(TreeNode *root, double target) {  
34:      while (root) {  
35:        if (root->val == target) {  
36:          pred.push(root);  
37:          break;  
38:        } else if (root->val < target) {  
39:          pred.push(root);  
40:          root = root->right;  
41:        } else {  
42:          root = root->left;  
43:        }  
44:      }  
45:    }  
46:    void initSuccessor(TreeNode *root, double target) {  
47:      while (root) {  
48:        if (root->val == target) {  
49:          succ.push(root);  
50:          break;  
51:        } else if (root->val > target) {  
52:          succ.push(root);  
53:          root = root->left;  
54:        } else {  
55:          root = root->right;  
56:        }  
57:      }  
58:    }  
59:    int getNextPredecessor() {  
60:      TreeNode *root = pred.top();  
61:      pred.pop();  
62:      int res = root->val;  
63:      root = root->left;  
64:      while (root) {  
65:        pred.push(root);  
66:        root = root-&gt;right;  
67:      }  
68:      return res;  
69:    }  
70:    int getNextSuccessor() {  
71:      TreeNode *root = succ.top();  
72:      succ.pop();  
73:      int res = root->val;  
74:      root = root->right;  
75:      while (root) {  
76:        succ.push(root);  
77:        root = root->left;  
78:      }  
79:      return res;  
80:    }  
81:  };  

The second time I revisited this problem, I found that initPredecessor() and initSuccessor() can be combined into one function.

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:  private:  
12:    stack<TreeNode *> pred;  
13:    stack<TreeNode *> succ;  
14:  public:  
15:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
16:      vector<int> res;  
17:      if (root == NULL) return res;  
18:      initStacks(root, target);  
19:      while (k) {  
20:        if (pred.empty()) res.push_back(getNextPredecessor());  
21:        else if (succ.empty()) res.push_back(getNextSuccessor());  
22:        else if (abs(pred.top()->val-target) < abs(succ.top()->val-target)) {  
23:          res.push_back(getNextPredecessor());  
24:        } else {  
25:          res.push_back(getNextSuccessor());  
26:        }  
27:        k--;  
28:      }  
29:      return res;  
30:    }  
31:    void initStacks(TreeNode *root, double target) {  
32:      while (root != NULL) {  
33:        if (root->val <= target) {  
34:          pred.push(root);  
35:          root = root->right;  
36:        } else {  
37:          succ.push(root);  
38:          root = root->left;  
39:        }  
40:      }  
41:    }  
42:    int getNextPredecessor() {  
43:      TreeNode *t = pred.top();  
44:      int ret = t->val;  
45:      pred.pop();  
46:      t = t->left;  
47:      while (t) {  
48:        pred.push(t);  
49:        t = t->right;  
50:      }  
51:      return ret;  
52:    }  
53:    int getNextSuccessor() {  
54:      TreeNode *t = succ.top();  
55:      int ret = t->val;  
56:      succ.pop();  
57:      t = t->right;  
58:      while (t) {  
59:        succ.push(t);  
60:        t = t->left;  
61:      }  
62:      return ret;  
63:    }  
64:  };  

99. Recover Binary Search Tree

My initial idea is to output all nodes into an array. Since it is a binary search tree, an in-order traversal should get us a sorted array. All we need to do then is to find two nodes that are out of order and swap then. The easy mistake to make is to use if else clause in finding the two node. Note these two nodes are not exclusive to each other, so we shouldn't do "else".

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:  private:  
12:    vector<TreeNode*> res;  
13:  public:  
14:    void recoverTree(TreeNode* root) {  
15:      helper(root);  
16:      TreeNode *first = NULL, *second = NULL;  
17:      for (int i = 0; i < res.size()-1; i++) {  
18:        if (first == NULL && res[i]->val > res[i+1]->val) {  
19:          first = res[i];  
20:        }  
21:        if (first != NULL && res[i]->val > res[i+1]->val) {  
22:          second = res[i+1];  
23:        }  
24:      }  
25:      swap(first->val, second->val);  
26:    }  
27:    void helper(TreeNode* root) {  
28:      if (root == NULL) return;  
29:      helper(root->left);  
30:      res.push_back(root);  
31:      helper(root->right);  
32:    }  
33:  };  

There is another way to find out the two out-of-order nodes within the in-order traversal. It's very important to let the previous node be a global variable. Because when you are traversing left child, when you are done, you want the previous node to be the left child. If you pass the previous node to the recursion, you are only considering the case of right child.

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:  private:  
12:    TreeNode *first = NULL;  
13:    TreeNode *second = NULL;  
14:    TreeNode *prev = new TreeNode(INT_MIN);  
15:  public:  
16:    void recoverTree(TreeNode* root) {  
17:      helper(root);  
18:      swap(first->val, second->val);  
19:    }  
20:    void helper(TreeNode *root) {  
21:      if (root == NULL) return;  
22:      helper(root->left);  
23:      if (first == NULL && prev->val >= root->val) first = prev;  
24:      if (first != NULL && prev->val >= root->val) second = root;  
25:      prev = root;  
26:      helper(root->right);  
27:    }  
28:  };  

98. Validate Binary Search Tree

In first place, I made a mistake that I only recursively compare the parent with its left and right child. This is incorrect. Note for a BST, all the nodes left child subtree are less than the root and on the other hand, all the nodes in right child subtree are larger than the root. Therefore, when doing the recursive call, we need to compare the current node with a minimal node and a maximal node. For the left subtree, the maximal node is the current node and for the right subtree, the minimal node is the current node. Also, the recursive function follows inorder 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:    bool isValidBST(TreeNode* root) {  
13:      return helper(root, NULL, NULL);  
14:    }  
15:    bool helper(TreeNode *root, TreeNode *minNode, TreeNode *maxNode) {  
16:      if (root == NULL) return true;  
17:      if (minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val) {  
18:        return false;  
19:      }  
20:      return helper(root->left, minNode, root) && helper(root->right, root, maxNode);  
21:    }  
22:  };  

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:  };  

106. Construct Binary Tree from Inorder and Postorder Traversal

A typical recursive solution. Must be familiar with the property of inorder and postorder traversal.
(1) With postorder traversal, the root must be the last element in the array.
(2) With inorder traversal, the subarray on root's left forms the left child subtree and the subarray on root's right forms the right child subtree.
With the two properties above, we can solve the problem recursive.

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>& inorder, vector<int>& postorder) {  
13:      if (inorder.empty()) return NULL;  
14:      return helper(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);  
15:    }  
16:    TreeNode *helper(vector<int> &inorder, int is, int ie, vector<int> &postorder, int ps, int pe) {  
17:      if (ie < is || pe < ps) return NULL;  
18:      int i = is;  
19:      for (;i < ie; i++) {  
20:        if (inorder[i] == postorder[pe]) break;  
21:      }  
22:      TreeNode *node = new TreeNode(postorder[pe]);  
23:      node->left = helper(inorder, is, i-1, postorder, ps, ps+i-is-1);  
24:      node->right = helper(inorder, i+1, ie, postorder, ps+i-is, pe-1);  
25:      return node;  
26:    }  
27:  };  

Note we have a loop to find the root position in inorder array. We can actually improve the algorithm by hashmap the value and its position first.