LeetCode刷题day39

LeetCode刷题day39

今日刷题重点—构造二叉树

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

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

3 / \ 9 20 / \ 15 7

思路分析

中序和后序构建树的思路:以后序最后一个节点为分割点,对中序进行分割,分割成左中序和右中序;之后根据左中序和右中序的长度再对后序进行分割,分割成左后序和右后序

图解如下:

具体实现步骤如下:

判断后序数组是否为0,如果为0则说明是空节点了.如果不为0,取后序元素的最后一个元素为根构建子树,同时以该元素为分割点.根据切割点切割中序数组,把中序数组分成左中序和右中序.根据分成的左右中序的长度把后序数组分成左后序和右后序.传入左中序和左后序递归构建子树的左子树传入右中序和右后序递归构建子树的右子树

注意点:无论是哪种方法,都要对递归时数组范围进行确定,如左闭右开,这个原则一定要保持不变.

参考代码

// 方法一:参数传递为数组 TreeNode* traversal(vector& inorder,vector& 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 leftInorder(inorder.begin(),inorder.begin()+delimiterIndex); //右中序 [delimiterIndex+1,end) vector rightInorder(inorder.begin()+delimiterIndex+1,inorder.end()); postorder.resize(postorder.size()-1); //切割后序数组 根据上面两个中序数组大小进行切割 //左后序 [0,leftorder.size) vector leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size()); //右后序[leftorder.size(),end) vector rightPostorder(postorder.begin()+leftInorder.size(),postorder.end()); //进行递归 创建其左右子树. root->left = traversal(leftInorder,leftPostorder); root->right = traversal(rightInorder,rightPostorder); return root;}TreeNode* buildTree(vector& inorder, vector& postorder) { if(!inorder.size() || !postorder.size()) { return NULL; } return traversal(inorder,postorder);}

参考代码2

以上代码在每次递归时都需要新创建数组,并且参数传递的都是数组.其实每次只需要把需要递归的数组范围下标传入就可.

//参数传递为下标. TreeNode* traversal(vector& inorder,int inorderBegin,int inorderEnd, vector& 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& inorder, vector& 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& preorder, vector& 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:"< leftInorder(inorder.begin(),inorder.begin()+delimiterIndex); //右中序 [delimiterIndex+1,end) vector rightInorder(inorder.begin()+delimiterIndex+1,inorder.end()); //分割先序序列 //左先序 [preorder.begin()+1) vector leftPreorder(preorder.begin()+1,preorder.begin()+1+leftInorder.size()); //右先序 vector rightPreorder(preorder.begin()+1+leftInorder.size(),preorder.end()); root->left = traversal(leftPreorder,leftInorder); root->right = traversal(rightPreorder,rightInorder); return root; } TreeNode* buildTree(vector& preorder, vector& inorder) { if(preorder.size()==0||inorder.size()==0){ return NULL; } return traversal(preorder,inorder);}

参考代码2

TreeNode* traversal(vector& preorder,int preorderBegin,int preorderEnd, vector& 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& preorder, vector& 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 ABCDEFGBCAD CBAD

样例2

ACBFGEDCDAB

思路分析

由于我们只是要求根据先序和中序输出后序,所以可以边递归边输出.

参考代码1—参数传递为字符串

#includeusing 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<>preorder>>inorder) { postorder(preorder,inorder); //cout<

参考代码2—参数传递为下标

#includeusing 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>>inorder) { int len=preorder.size(); postorder(0,0,len); cout<

​​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& nums) { // if(nums.size()==1) { //如果只有一个叶子节点 这个结束条件可加可不加,因为我们在下面构建左子树和右子树时也进行了判断. // node->val = nums[0];// return node;// } //找到数组中最大的值和对应的下标 int maxValue = 0; int maxValueIndex = 0; for(int i = 0; i newVec(nums.begin(),nums.begin()+maxValueIndex); node->left = constructMaximumBinaryTree(newVec); } //构造右子树 if(maxValueIndex newVec(nums.begin()+maxValueIndex+1,nums.end()); node->right = constructMaximumBinaryTree(newVec); } return node;}

参考代码2—参数传递为下标

递归三部曲:

确定参数和返回值:参数为原始数组,需要递归的数组的范围下标. 返回值为子树的根节点.确定结束条件:当left>=right表示当前没有节点传入来构建子树.返回NULL(我们采用的是左闭右开区间)确定单层递归逻辑:确定最大值,并以该值为根节点创建子树,同时以该节点为分割点,进行左递归和右递归.

TreeNode* traversal(vector& 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& nums) { return traversal(nums,0,nums.size());}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。