leetcode

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