156. Binary Tree Upside Down

Postorder traversal and then construct the tree from downside to upside.

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* upsideDownBinaryTree(TreeNode* root) {  
13:      if (root == NULL) return root;  
14:      TreeNode *res = root;  
15:      while (res->left) res = res->left;  
16:      helper(root);  
17:      return res;  
18:    }  
19:    TreeNode *helper(TreeNode *root) {  
20:      if (root->left == NULL && root->right == NULL) return root;  
21:      TreeNode *nr = helper(root->left);  
22:      nr->left = root->right;  
23:      nr->right = root;  
24:      root->left = NULL;  
25:      root->right = NULL;  
26:      return root;  
27:    }  
28:  };  

145. Binary Tree Postorder Traversal

My intuition is to use stack. But, first time I write the solution, I got TLE for case [1, null, 2]. Then I checked the logic again and find that the problem is in line 23. I notice that the root 1 will be visited twice. When we are done with left child, we’ll visit root once and we goes into right child. And then when we are done with right child, we’ll visit root again. At this time, we don’t want to go visit right child again but pop out the root. So we need to an extra pointer to keep the last node we visited. If the last node is the right child, we know that we are done with visiting children and we need to pop out root.

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> postorderTraversal(TreeNode* root) {  
13:      vector<int> res;  
14:      stack<TreeNode *> stk;  
15:      TreeNode *cur = root;  
16:      TreeNode *last = NULL;  
17:      while (cur || !stk.empty()) {  
18:        if (cur) {  
19:          stk.push(cur);  
20:          cur = cur->left;  
21:        } else {  
22:          TreeNode *top = stk.top();  
23:          if (top->right && top->right != last) {  
24:            cur = top->right;  
25:          } else {  
26:            res.push_back(top->val);  
27:            last = top;  
28:            stk.pop();  
29:          }  
30:        }  
31:      }  
32:      return res;  
33:    }  
34:  };  

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.