leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0106.cpp (948B)

      1 class Solution {
      2     class Record {
      3       public:
      4         int low, high;
      5         TreeNode **field;
      6         Record(int l, int h, TreeNode **f) : low(l), high(h), field(f) {}
      7     };
      8 
      9   public:
     10     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
     11         unordered_map<int, int> um;
     12         for (int i = 0; i < inorder.size(); i++)
     13             um[inorder[i]] = i;
     14 
     15         int crnt = postorder.size() - 1;
     16         TreeNode head, *nw;
     17         stack<Record> st;
     18 
     19         st.push({0, (int)inorder.size(), &head.right});
     20         while (!st.empty()) {
     21             Record r = st.top();
     22             st.pop();
     23             while (r.low < r.high) {
     24                 int pos = um[postorder[crnt]];
     25                 nw = *r.field = new TreeNode(postorder[crnt--]);
     26                 st.push({r.low, pos, &nw->left});
     27                 r.low = pos + 1;
     28                 r.field = &nw->right;
     29             }
     30         }
     31         return head.right;
     32     }
     33 };