从中序与后序遍历序列构造二叉树-力扣

本文主要是介绍从中序与后序遍历序列构造二叉树-力扣，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

中序遍历序列存放节点的顺序是左中右，后序遍历存放节点的顺序是左右中
后序遍历序列的最后一个节点即为二叉树的根节点
由于每个值在二叉树中都是唯一的，那么根据根节点的值，就可以将中序遍历序列一分为二，前部分存储的是根节点左子树的节点，后半部分存储的是根节点右子树的节点
不论中序还是后序遍历，左右子树的节点是相同的，那么就可以将两个序列划分为四个序列，中序遍历序列的左右部分，后序遍历序列的左右部分
那么此时，以根节点的值构造根节点，根节点的左子节点，就可以以中序遍历序列的左部分和后序遍历序列的左部分进行构造，右子节点同理
那么递归下去，就能够构造完成整棵二叉树
注：在实现时，对 inorderleft 等四个数组未进行初始化，规定数组的大小，此时是无法 inorderleft[i] = inorder[i]; 这样去赋值的。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* subVec(vector<int> inorder, vector<int> postorder){if(inorder.empty() && postorder.empty()){return nullptr;}TreeNode* root = new TreeNode(postorder[postorder.size() - 1]);if(postorder.size() == 1){return root;}int flag = 0;for(flag; flag < inorder.size(); flag++){if(inorder[flag] == root->val){break;}}vector<int> inorderleft;vector<int> inorderright;vector<int> postorderleft;vector<int> postorderright;for(int i = 0; i < flag; i++){inorderleft.push_back(inorder[i]);postorderleft.push_back(postorder[i]);}for(int j = flag; j + 1 < inorder.size(); j++){inorderright.push_back(inorder[j + 1]);postorderright.push_back(postorder[j]);}root->left = subVec(inorderleft, postorderleft);root->right = subVec(inorderright, postorderright);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {TreeNode* root = subVec(inorder, postorder);return root;}
};