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

• 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

代码/**

• Definition for a binary tree node.

• struct TreeNode {

• int val;
  

• TreeNode *left;
  

• TreeNode *right;
  

• TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  

• };
  /
  class Solution {
  public:
  unordered_map<int, int> pos;
  TreeNode buildTree(vector& inorder, vector& postorder) {
  for (int i = 0; i < inorder.size(); ++i) pos[inorder[i]] = i;
  return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
  }

  TreeNode* build(vector& inorder, vector& postorder, int il, int ir, int pl, int pr) {
  if (il > ir) return NULL;
  auto root = new TreeNode(postorder[pr]);
  int k = pos[root->val];
  root->left = build(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);
  root->right = build(inorder, postorder, k + 1, ir, pl + k - il, pr - 1);
  return root;
  }
  };