天天看点
返回

LeetCode刷题day39

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

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

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

注意:

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

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3
   / \
  9  20
    /  \
   15   7

思路分析

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

图解如下:

LeetCode刷题day39

具体实现步骤如下:

  • 判断后序数组是否为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:

LeetCode刷题day39
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：

LeetCode刷题day39
输入：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：

LeetCode刷题day39
输入：nums = [3,2,1]
输出：[3,null,2,null,1]

思路分析

构造树一般采用先序遍历,先构造根节点再构造左子树,右子树.

图解如下:

LeetCode刷题day39
  • 参数和返回值:参数为要构建树的数组,返回值为该子树构建完成后的子树根节点.
  • 确定结束条件:每次当数组只有一个节点时,说明该节点是叶子节点,创建该节点后直接返回即可,无需后序的递归.(当然也可以不用该结束条件,因为递归前有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());
}
leetcode 算法 数据结构 二叉树 数组
上一篇: 如何用python画散点图矩阵_如何用python画出样本的散点图？
下一篇: Pandas读写Excel函数大全

继续阅读