leetcode

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

0105.cpp (912B)

      1 class Solution {
      2     typedef vector<int>::iterator vii;
      3     struct Record {
      4         TreeNode **fill = nullptr;
      5         vii start, end;
      6         Record(TreeNode **f, vii s, vii e) : fill(f), start(s), end(e) {}
      7     };
      8 
      9   public:
     10     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
     11         stack<Record> st;
     12         TreeNode head;
     13         int pre = 0;
     14 
     15         st.push({&head.right, inorder.begin(), inorder.end()});
     16         while (!st.empty()) {
     17             Record r = st.top();
     18             st.pop();
     19             while (r.start < r.end) {
     20                 vii mid = find(r.start, r.end, preorder[pre]);
     21                 if (mid == r.end) break;
     22                 TreeNode *n = *r.fill = new TreeNode(preorder[pre++]);
     23                 st.push({&n->right, next(mid), r.end});
     24                 r.end = mid;
     25                 r.fill = &n->left;
     26             }
     27         }
     28 
     29         return head.right;
     30     }
     31 };