【leetcode】通过两种遍历方式构造二叉树

 分治法：先构造出当前根节点，再递归构造左子树，递归构造右子树，核心是找到左子树、右子树对应的遍历序列：先构造一个hash表存储 一个序列中每个节点的索引，再通过另外一个序列计算出左子树、右子树对应的遍历序列的长度

class Solution {
public:unordered_map <int,int> idx;TreeNode* tree(vector<int>& preorder, vector<int>& inorder,int preleft,int preright,int inleft,int inright){if(preleft > preright)return NULL;TreeNode* root=new TreeNode(preorder[preleft]);int root_index=idx[preorder[preleft]];int sub_left_tree_size=root_index-inleft;root->left=tree(preorder, inorder,preleft+1,preleft+sub_left_tree_size,inleft,root_index-1);root->right=tree(preorder, inorder,preleft+sub_left_tree_size+1,preright,root_index+1,inright);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for(int i=0;i<inorder.size();i++)idx[inorder[i]]=i;return tree(preorder,inorder,0,inorder.size()-1,0,inorder.size()-1);}
};

class Solution {
public:unordered_map <int,int> index;TreeNode* mytree(vector<int>& inorder, vector<int>& postorder, int inorder_left,int inorder_right,int postorder_left,int postorder_right){if(postorder_left>postorder_right)return NULL;TreeNode* root=new TreeNode(postorder[postorder_right]);int root_idx=index[postorder[postorder_right]];int sub_left_tree_num=root_idx-inorder_left;root->left=mytree(inorder,postorder,inorder_left,root_idx-1,postorder_left,postorder_left+sub_left_tree_num-1);root->right=mytree(inorder,postorder,root_idx+1,inorder_right,postorder_left+sub_left_tree_num,postorder_right-1);return root;    }TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n=inorder.size();for(int i=0;i<inorder.size();i++)index[inorder[i]]=i;return mytree(inorder,postorder,0,n-1,0,n-1);}
};

 

class Solution {
public:unordered_map <int,int> index;TreeNode* mytree(vector<int>& preorder, vector<int>& postorder,int preorder_left,int preorder_right,int postorder_left,int postorder_right){if(preorder_left > preorder_right)return NULL;TreeNode* root=new TreeNode(preorder[preorder_left]);if(preorder_left==preorder_right)return root;int root_left_idx=index[preorder[preorder_left+1]];int sub_left_tree_num=root_left_idx-postorder_left+1; //注意左子树的node数量计算方式root->left=mytree(preorder,postorder,preorder_left+1,preorder_left+sub_left_tree_num,postorder_left,postorder_left+sub_left_tree_num-1);root->right=mytree(preorder,postorder,preorder_left+sub_left_tree_num+1,preorder_right,postorder_left+sub_left_tree_num,postorder_right-1);return root;}TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {int n=postorder.size();for(int i=0;i<n;i++)index[postorder[i]]=i;return mytree(preorder,postorder,0,n-1,0,n-1);}};