1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
#include <unordered_map> #include <vector>
class Solution { public: TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) { std::unordered_map<int, int> inorder_map; for (size_t i = 0; i < inorder.size(); ++i) { inorder_map[inorder[i]] = i; } return buildTree(postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1, inorder_map); }
private: TreeNode* buildTree(const std::vector<int>& postorder, const std::vector<int>& inorder, int postorder_begin, int postorder_end, int inorder_begin, int inorder_end, std::unordered_map<int, int>& inorder_map) { if (postorder_end < postorder_begin || inorder_end < inorder_begin) return nullptr; TreeNode* root = new TreeNode(postorder[postorder_end]); int root_idx = inorder_map[root->val]; int left_len = root_idx - inorder_begin; int right_len = inorder_end - root_idx; root->left = buildTree(postorder, inorder, postorder_begin, postorder_begin + left_len - 1, inorder_begin, root_idx - 1, inorder_map); root->right = buildTree(postorder, inorder, postorder_begin + left_len, postorder_end - 1, root_idx + 1, inorder_end, inorder_map);
return root; } };
|