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

根据中序遍历和后序遍历的性质，还原二叉树，详细见注释 

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//空，直接返回nullif(inorder.size() == 0) return nullptr;//一个，返回一个node结点if(inorder.size() == 1) return new TreeNode(inorder[0]);int size = postorder.size();int val = postorder[size-1];//后续遍历的最后一个元素是根节点TreeNode* root = new TreeNode(val);//在中序中找到根节点的位置auto idx1 = find(inorder.begin(), inorder.end(), val);//中序遍历中根节点的位置左侧是左子树中序遍历，右侧为右子树中序遍历//分别拷贝构造出新的中序遍历vectorvector<int> inorder_left(inorder.begin(), idx1);vector<int> inorder_right(idx1+1, inorder.end());int left_num = inorder_left.size();//后序遍历左子树等于后序遍历起点+中序遍历左子树vector.size()vector<int> postorder_left(postorder.begin(), postorder.begin()+left_num);//后边遍历右子树等于后序遍历左子树下一个元素到倒数第二个元素vector<int> postorder_right(postorder.begin()+left_num, postorder.end()-1);//构造左右子树root->left = buildTree(inorder_left, postorder_left);root->right = buildTree(inorder_right, postorder_right);return root;}