106. 从中序与后序遍历序列构造二叉树

  1. class Solution {
  2. private:
  3. TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
  4. if (postorder.size() == 0) return NULL;
  5. // 后序遍历数组最后一个元素,就是当前的中间节点
  6. int rootValue = postorder[postorder.size() - 1];
  7. TreeNode* root = new TreeNode(rootValue);
  8. // 叶子节点
  9. if (postorder.size() == 1) return root;
  10. // 找到中序遍历的切割点
  11. int delimiterIndex;
  12. for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
  13. if (inorder[delimiterIndex] == rootValue) break;
  14. }
  15. // 切割中序数组
  16. // 左闭右开区间:[0, delimiterIndex)
  17. vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
  18. // [delimiterIndex + 1, end)
  19. vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
  20. // postorder 舍弃末尾元素
  21. postorder.resize(postorder.size() - 1);
  22. // 切割后序数组
  23. // 依然左闭右开,注意这里使用了左中序数组大小作为切割点
  24. // [0, leftInorder.size)
  25. vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
  26. // [leftInorder.size(), end)
  27. vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
  28. root->left = traversal(leftInorder, leftPostorder);
  29. root->right = traversal(rightInorder, rightPostorder);
  30. return root;
  31. }
  32. public:
  33. TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  34. if (inorder.size() == 0 || postorder.size() == 0) return NULL;
  35. return traversal(inorder, postorder);
  36. }
  37. };

优化

  1. class Solution {
  2. private:
  3. // 中序区间:[inorderBegin, inorderEnd),后序区间[postorderBegin, postorderEnd)
  4. TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
  5. if (postorderBegin == postorderEnd) return NULL;
  6. int rootValue = postorder[postorderEnd - 1];
  7. TreeNode* root = new TreeNode(rootValue);
  8. if (postorderEnd - postorderBegin == 1) return root;
  9. int delimiterIndex;
  10. for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
  11. if (inorder[delimiterIndex] == rootValue) break;
  12. }
  13. // 切割中序数组
  14. // 左中序区间,左闭右开[leftInorderBegin, leftInorderEnd)
  15. int leftInorderBegin = inorderBegin;
  16. int leftInorderEnd = delimiterIndex;
  17. // 右中序区间,左闭右开[rightInorderBegin, rightInorderEnd)
  18. int rightInorderBegin = delimiterIndex + 1;
  19. int rightInorderEnd = inorderEnd;
  20. // 切割后序数组
  21. // 左后序区间,左闭右开[leftPostorderBegin, leftPostorderEnd)
  22. int leftPostorderBegin = postorderBegin;
  23. int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
  24. // 右后序区间,左闭右开[rightPostorderBegin, rightPostorderEnd)
  25. int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
  26. int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素,已经作为节点了
  27. root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
  28. root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
  29. return root;
  30. }
  31. public:
  32. TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  33. if (inorder.size() == 0 || postorder.size() == 0) return NULL;
  34. // 左闭右开的原则
  35. return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
  36. }
  37. };

使用哈希表记录索引

先构建所有右子树,再构建左子树

  1. class Solution {
  2. int post_idx;
  3. unordered_map<int, int> idx_map;
  4. public:
  5. TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
  6. // 如果这里没有节点构造二叉树了,就结束
  7. if (in_left > in_right) {
  8. return nullptr;
  9. }
  10. // 选择 post_idx 位置的元素作为当前子树根节点
  11. int root_val = postorder[post_idx];
  12. TreeNode* root = new TreeNode(root_val);
  13. // 根据 root 所在位置分成左右两棵子树
  14. int index = idx_map[root_val];
  15. // 下标减一
  16. post_idx--;
  17. // 构造右子树
  18. root->right = helper(index + 1, in_right, inorder, postorder);
  19. // 构造左子树
  20. root->left = helper(in_left, index - 1, inorder, postorder);
  21. return root;
  22. }
  23. TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  24. // 从后序遍历的最后一个元素开始
  25. post_idx = (int)postorder.size() - 1;
  26. // 建立(元素,下标)键值对的哈希表
  27. int idx = 0;
  28. for (auto& val : inorder) {
  29. idx_map[val] = idx++;
  30. }
  31. return helper(0, (int)inorder.size() - 1, inorder, postorder);
  32. }
  33. };