leetcode

0 class Solution {

1 typedef vector<int>::iterator vii;

2 struct Record {

3 TreeNode **fill = nullptr;

4 vii start, end;

5 Record(TreeNode **f, vii s, vii e) : fill(f), start(s), end(e) {}

6 };

7

8 public:

9 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

10 stack<Record> st;

11 TreeNode head;

12 int pre = 0;

13

14 st.push({&head.right, inorder.begin(), inorder.end()});

15 while (!st.empty()) {

16 Record r = st.top();

17 st.pop();

18 while (r.start < r.end) {

19 vii mid = find(r.start, r.end, preorder[pre]);

20 if (mid == r.end) break;

21 TreeNode *n = *r.fill = new TreeNode(preorder[pre++]);

22 st.push({&n->right, next(mid), r.end});

23 r.end = mid;

24 r.fill = &n->left;

25 }

26 }

27

28 return head.right;

29 }

30 };