leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0106.cpp (948B)

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