1. 由中序和后续构造二叉树

image.png
image.png

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int pos; // 后序遍历，根节点index
  15.     unordered_map<int, int> mp; // 中序遍历, val->index
  16.     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  17.         pos = (int)postorder.size() - 1;
  18.         for (int i = 0; i < inorder.size(); i++) {
  19.             mp[inorder[i]] = i;
  20.         }
  21.         return dfs(0, pos, postorder);
  22.     }
  23.     // left, right 是中序的index
  24.     TreeNode* dfs(int left, int right, vector<int>& postorder) {
  25.         if (left > right) {
  26.             return nullptr;
  27.         }
  28.         int rootVal = postorder[pos];
  29.         TreeNode* root = new TreeNode(rootVal);
  30.         int inIndex = mp[rootVal]; // 根节点在中序的位置
  31.         pos--;
  32.         root->right = dfs(inIndex + 1, right, postorder);
  33.         root->left = dfs(left, inIndex - 1, postorder);
  34.         return root;
  35.     }
  36. };