今日刷题重点—构造二叉树
106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3 / \ 9 20 / \ 15 7
思路分析
中序和后序构建树的思路:以后序最后一个节点为分割点,对中序进行分割,分割成左中序和右中序;之后根据左中序和右中序的长度再对后序进行分割,分割成左后序和右后序
图解如下:
判断后序数组是否为0,如果为0则说明是空节点了.
如果不为0,取后序元素的最后一个元素为根构建子树,同时以该元素为分割点.
根据切割点切割中序数组,把中序数组分成左中序和右中序.
根据分成的左右中序的长度把后序数组分成左后序和右后序.
传入左中序和左后序递归构建子树的左子树
传入右中序和右后序递归构建子树的右子树
注意点:无论是哪种方法,都要对递归时数组范围进行确定,如左闭右开,这个原则一定要保持不变.
参考代码
// 方法一:参数传递为数组 TreeNode* traversal(vector<int>& inorder,vector<int>& postorder) { if(postorder.size()==0) { return NULL; } //获取当前的中间节点--对应后序数组的最后一个 int rootValue = postorder[postorder.size()-1]; //以该节点为根创建新的子树 TreeNode* root = new TreeNode(rootValue); // 找到中序遍历的切割点. int delimiterIndex; for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { if(inorder[delimiterIndex]==rootValue) { break; } } //切割中序数组 //左中序左闭右开区间 [0,delimiterIndex) vector<int> leftInorder(inorder.begin(),inorder.begin()+delimiterIndex); //右中序 [delimiterIndex+1,end) vector<int> rightInorder(inorder.begin()+delimiterIndex+1,inorder.end()); postorder.resize(postorder.size()-1); //切割后序数组 根据上面两个中序数组大小进行切割 //左后序 [0,leftorder.size) vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size()); //右后序[leftorder.size(),end) vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end()); //进行递归 创建其左右子树. root->left = traversal(leftInorder,leftPostorder); root->right = traversal(rightInorder,rightPostorder); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(!inorder.size() || !postorder.size()) { return NULL; } return traversal(inorder,postorder); }
参考代码2
以上代码在每次递归时都需要新创建数组,并且参数传递的都是数组.其实每次只需要把需要递归的数组范围下标传入就可.
//参数传递为下标. TreeNode* traversal(vector<int>& inorder,int inorderBegin,int inorderEnd, vector<int>& postorder,int postorderBegin,int postorderEnd) { if(postorderBegin==postorderEnd){ return NULL; } //获取当前的中间节点--对应后序数组的最后一个 int rootValue = postorder[postorderEnd-1]; //以该节点为根创建新的子树 TreeNode* root = new TreeNode(rootValue); // 找到中序遍历的切割点. int delimiterIndex; for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) { if(inorder[delimiterIndex]==rootValue) { break; } } //切割中序数组 //左中序左闭右开区间 [leftInorderBegin,leftInorderEnd) int leftInorderBegin = inorderBegin; int leftInorderEnd = delimiterIndex; //右中序 [rightInorderBegin+1,end) int rightInorderBegin = delimiterIndex + 1; int rightInorderEnd = inorderEnd; //切割后序数组 根据上面两个中序数组大小进行切割 //左后序 [leftPostorderBegin,leftPostorderEnd) int leftPostorderBegin = postorderBegin; int leftPostorderEnd = postorderBegin+delimiterIndex-inorderBegin;//终止位置 //右后序[leftorder.size(),end) int rightPostorderBegin = postorderBegin+delimiterIndex-inorderBegin; int rightPostorderEnd = postorderEnd-1;//排除最后一个元素,已经作为节点了 //进行递归 创建其左右子树. root->left = traversal(inorder,leftInorderBegin,leftInorderEnd,postorder,leftPostorderBegin,leftPostorderEnd); root->right = traversal(inorder,rightInorderBegin,rightInorderEnd,postorder,rightPostorderBegin,rightPostorderEnd); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(!inorder.size() || !postorder.size()) { return NULL; } return traversal(inorder,0,inorder.size(),postorder,0,postorder.size()); }
105. 从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
思路分析
思路和步骤和上面那种方法基本相同.
参考代码1
TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){ if(preorder.size()==0){ return NULL; } int rootValue = preorder[0]; TreeNode* root = new TreeNode(rootValue); //寻找切割点 int delimiterIndex; for(delimiterIndex = 0;delimiterIndex < inorder.size();delimiterIndex++){ if(inorder[delimiterIndex] == rootValue){ break; } } // cout<<"delimiterIndex:"<<delimiterIndex<<endl; //分割中序序列. //左中序 左闭右开[0,delimiterIndex) vector<int> leftInorder(inorder.begin(),inorder.begin()+delimiterIndex); //右中序 [delimiterIndex+1,end) vector<int> rightInorder(inorder.begin()+delimiterIndex+1,inorder.end()); //分割先序序列 //左先序 [preorder.begin()+1) vector<int> leftPreorder(preorder.begin()+1,preorder.begin()+1+leftInorder.size()); //右先序 vector<int> rightPreorder(preorder.begin()+1+leftInorder.size(),preorder.end()); root->left = traversal(leftPreorder,leftInorder); root->right = traversal(rightPreorder,rightInorder); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size()==0||inorder.size()==0){ return NULL; } return traversal(preorder,inorder); }
参考代码2
TreeNode* traversal(vector<int>& preorder,int preorderBegin,int preorderEnd, vector<int>& inorder,int inorderBegin,int inorderEnd){ if(preorderBegin==preorderEnd){ return NULL; } int rootValue = preorder[preorderBegin]; TreeNode* root = new TreeNode(rootValue); //寻找切割点 int delimiterIndex; for(delimiterIndex = inorderBegin;delimiterIndex < inorderEnd;delimiterIndex++){ if(inorder[delimiterIndex]==rootValue){ break; } } //分割中序序列. //左中序 [leftInorderBegin,leftInorderEnd) int leftInorderBegin = inorderBegin; int leftInorderEnd = delimiterIndex; //右中序 [rightInorderBegin,rightInorderEnd) int rightInorderBegin = delimiterIndex + 1; int rightInorderEnd = inorderEnd; //分割前序序列 //左前序[leftPreorderBegin,leftPreorderEnd) int leftPreorderBegin = preorderBegin + 1; int leftPreorderEnd = preorderBegin+1+leftInorderEnd-leftInorderBegin; //右先序 [rightPreorderBegin,rightPreorderEnd) int rightPreorderBegin = preorderBegin+1+leftInorderEnd-leftInorderBegin; int rightPreorderEnd = preorderEnd; root->left = traversal(preorder,leftPreorderBegin,leftPreorderEnd,inorder,leftInorderBegin,leftInorderEnd); root->right = traversal(preorder,rightPreorderBegin,rightPreorderEnd,inorder,rightInorderBegin,rightInorderEnd); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size()==0||inorder.size()==0){ return NULL; } return traversal(preorder,0,preorder.size(),inorder,0,inorder.size()); }
UVA536 二叉树重建 Tree Recovery
输入一棵二叉树的先序遍历和中序遍历序列，输出它的后序遍历序列。
样例1
DBACEGF ABCDEFG BCAD CBAD
样例2
ACBFGED CDAB
思路分析
由于我们只是要求根据先序和中序输出后序,所以可以边递归边输出.
参考代码1—参数传递为字符串
#include<bits/stdc++.h> using namespace std; string preorder,inorder; void postorder(string pre,string in) { if(pre.size()<=0) return; int len=0; // while(in[len]!=pre[0])//在中序中找到的根结点的位置 // { // len++; // } len=in.find(pre[0]);//返回其位置 postorder(pre.substr(1,len),in.substr(0,len)); postorder(pre.substr(len+1),in.substr(len+1)); cout<<pre[0]; } int main() { while(cin>>preorder>>inorder) { postorder(preorder,inorder); //cout<<inorder.find(preorder[0]); cout<<endl; } return 0; }
参考代码2—参数传递为下标
#include<bits/stdc++.h> using namespace std; string preorder,inorder; void postorder(int l1,int l2,int n) { if(n<=0) return; int len=inorder.find(preorder[l1])-l2;//返回其位置 postorder(l1+1,l2,len); postorder(l1+len+1,l2+len+1,n-len-1); cout<<preorder[l1]; } int main() { while(cin>>preorder>>inorder) { int len=preorder.size(); postorder(0,0,len); cout<<endl; } return 0; }
654. 最大二叉树
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
[3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
[3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
空数组，无子节点。
[2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
空数组，无子节点。
只有一个元素，所以子节点是一个值为 1 的节点。
[0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
只有一个元素，所以子节点是一个值为 0 的节点。
空数组，无子节点。
示例 2：
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
思路分析
构造树一般采用先序遍历,先构造根节点再构造左子树,右子树.
图解如下:
递归三要素:
参数和返回值:参数为要构建树的数组,返回值为该子树构建完成后的子树根节点.
确定结束条件:每次当数组只有一个节点时,说明该节点是叶子节点,创建该节点后直接返回即可,无需后序的递归.(当然也可以不用该结束条件,因为递归前有if条件控制,所以暗含有结束条件)
确定单层递归逻辑:先找到数组中最大的元素,以该元素为根创建子树;同时该元素将作为分割点,将数组分为左数组和右数组,然后递归创建左子树和右子树.
参考代码1—参数传递为数组.
TreeNode* constructMaximumBinaryTree(vector<int>& nums) { // if(nums.size()==1) { //如果只有一个叶子节点 这个结束条件可加可不加,因为我们在下面构建左子树和右子树时也进行了判断. // node->val = nums[0]; // return node; // } //找到数组中最大的值和对应的下标 int maxValue = 0; int maxValueIndex = 0; for(int i = 0; i <nums.size(); i++) { if(maxValue<nums[i]) { maxValue = nums[i]; maxValueIndex = i; } } TreeNode* node = new TreeNode(maxValue); //构造左子树 if(maxValueIndex) { //当 maxValueIndex = 0,无左子树 vector<int> newVec(nums.begin(),nums.begin()+maxValueIndex); node->left = constructMaximumBinaryTree(newVec); } //构造右子树 if(maxValueIndex<nums.size()-1) { //当 maxValueIndex= nums.size()-1时,无右子树 vector<int> newVec(nums.begin()+maxValueIndex+1,nums.end()); node->right = constructMaximumBinaryTree(newVec); } return node; }
参考代码2—参数传递为下标
递归三部曲:
确定参数和返回值:参数为原始数组,需要递归的数组的范围下标. 返回值为子树的根节点.
确定结束条件:当left>=right表示当前没有节点传入来构建子树.返回NULL(我们采用的是左闭右开区间)
确定单层递归逻辑:确定最大值,并以该值为根节点创建子树,同时以该节点为分割点,进行左递归和右递归.
TreeNode* traversal(vector<int>& nums,int left,int right) { if(left>=right) { return nullptr; } int maxValueIndex = left; for(int i = left+1; i< right; i++) { if(nums[i]>nums[maxValueIndex]) { maxValueIndex = i; } } TreeNode* node = new TreeNode(nums[maxValueIndex]); //构建左子树 [left,maxValueIndex) node->left = traversal(nums,left,maxValueIndex); //构建右子树 (maxValueIndex+1,right] node->right = traversal(nums,maxValueIndex+1,right); return node; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return traversal(nums,0,nums.size()); }
