精华内容
下载资源
问答
  • 已知中序遍历和前序遍历,求后序遍历思路前序遍历:根 左 右 中序遍历:左 根 右 寻找根,然后对于中序遍历,根的左半部分和前序遍历的根后面的左那部分 又重新构成一个相同的子问题,递归求解即可。Code#pragma ...

    已知中序遍历和前序遍历,求后序遍历

    思路

    前序遍历:根 左 右
    中序遍历:左 根 右
    寻找根,然后对于中序遍历,根的左半部分和前序遍历的根后面的左那部分 又重新构成一个相同的子问题,递归求解即可。

    Code

    #pragma once
    #include<iostream>
    #include<stack>
    #include<queue>
    using namespace std;
    typedef struct Node
    {
        int data;
        Node *left;
        Node *right;
    };
    Node *ConstructCore(int *StartPreorder, int *EndPreorder, int *StartInorder, int *EndInorder)
    {
        int rootvalue = StartPreorder[0];//根节点
        Node *root = new Node();
        root->data = rootvalue;
        root->left = root->right = NULL;
        int *rootInorder = StartInorder;
        if (StartPreorder == EndPreorder)
            return root;
    
        while (rootInorder <= EndInorder&&*rootInorder != rootvalue)
            rootInorder++;
        int len1 = rootInorder - StartInorder;
        if (len1 > 0)//构建左子树
        {
            root->left = ConstructCore(StartPreorder + 1, StartPreorder+len1, StartInorder, rootInorder-1);
        }
        if (len1 <EndPreorder- StartPreorder)//构建右子树
        {
            root->right = ConstructCore(StartPreorder + len1+1, EndPreorder, rootInorder + 1, EndInorder);
        }
        return root;
    }
    Node* Construct(int *Preorder, int *Inorder, int len)
    {
        if (Preorder == NULL || Inorder == NULL || len <= 0)
            return NULL;
        return ConstructCore(Preorder, Preorder + len - 1, Inorder, Inorder + len - 1);
    }
    

    测试

    int P[] = { 1,2,4,7,3,5,6,8 };
        int I[] = { 4,7,2,1,5,3,8,6 };
        int len = sizeof(P) / sizeof(int);
        Node *root = Construct(P, I, len);
        LastOrder111(root);

    7 4 2 5 8 6 3 1

    已知二叉树前序遍历和后序遍历如何求中序遍历?

    前序遍历:根 左 右
    后续遍历:左 右 根

    (应该是没有解吧!)因为无法区分左右啊!

    已知二叉树中序遍历和后序遍历如何求前序遍历?

    中序遍历:左 根 右
    后续遍历:左 右 根

    这个很简单,仿照第一种思路,先通过后续遍历找根节点,然后对中序遍历寻找左半部分和后序遍历左半部分一起递归寻找。
    大致代码如下:

    Node *ConstructCore1(int *StartInorder, int *EndInorder, int *StartLastorder, int *EndLastorder)
    {
        int rootvalue = *EndLastorder;//根节点
        Node *root = new Node();
        root->data = rootvalue;
        root->left = root->right = NULL;
        int *rootInorder = StartInorder;
        if (StartInorder== EndInorder)
            return root;
    
        while (rootInorder <= EndInorder&&*rootInorder != rootvalue)
            rootInorder++;
        int len1 = rootInorder - StartInorder;
        if (len1 > 0)//构建左子树
        {
            root->left = ConstructCore1(StartInorder, rootInorder-1, StartLastorder, StartLastorder+len1-1);
        }
        if (len1 <EndLastorder- StartLastorder)//构建右子树
        {
            root->right = ConstructCore1(rootInorder+1, EndInorder,StartLastorder+len1, EndLastorder-1);
        }
        return root;
    }
    Node* Construct1(int *Inorder, int *Lastorder, int len)
    {
        if (Inorder== NULL || Lastorder== NULL || len <= 0)
            return NULL;
        return ConstructCore1(Inorder, Inorder+ len - 1, Lastorder, Lastorder+ len - 1);
    }
    展开全文
  • 根据中序遍历和后续遍历(前序遍历)构造二叉树 首先说说递归:对于大部分人而言递归总是那么难,因为它的过程比较抽象和复杂,但是说到底递归也是分治法的思想只要我们求得 相同子问题的解法那么对每个子问题求解并且...

    根据中序遍历和后续遍历(前序遍历)构造二叉树

    首先说说递归:对于大部分人而言递归总是那么难,因为它的过程比较抽象和复杂,但是说到底递归也是分治法的思想只要我们求得
    相同子问题的解法那么对每个子问题求解并且合并就是我们整个递归的过程
    我们举个例子:
    假如一个树的
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    后序遍历 postorder = [9,15,7,20,3]

    那么我们可以这样拆解问题:
    我们首先分析前中序遍历:
    前序遍历的的第一个节点往往是我们的根节点
    root=3
    而后我们根据中序遍历可以把前序遍历分为两部分,把中序遍历也分为两部分,作为下层使用的前中序数组
    我们可以得到在中序遍历中3处在1下标
    那么分割后:
    leftinorder = [9]//左子树中序
    leftpreorder = [9]//左子树前序
    rightinorder = [15,20,7]//右子树中序
    rightpreorder = [20,15,7]//右子树前序

    看到这里大家肯定有点明白但是还是不知道代码如何写那么我们来看看规律:
    首先我们找到了3在中序遍历中的1处所以看看如下计算方法(不要问为什么这就是规律总结而来的)
    i//这个变量用来记录中遍历root的下标此时i==1
    leftinorder=Arrays.copyOfRange(inorder,0,i);//这个是java自带的数组工具作用是截取原数组形成新数组(左闭右开)
    leftpreorder=Arrays.copyOfRange(preorder,1,i+1);
    rightinorder=Arrays.copyOfRange(inorder,i+1,inorder.length);
    rightpreorder=Arrays.copyOfRange(preorder,i+1,preorder.length);

    //以上就是我们每层的前中序诞生逻辑
    然后我们看看每层怎么取root
    刚才说过每次进来取前序第一个元素为根节点(前序遍历特点)
    也就是说我们每层都要进行这样一次操作: TreeNode root=new TreeNode(preorder[0]);

    这样每层根节点就确定了,也就意味着我们每层的节点都有了(我们的二叉树可以分解为很多个二叉树,也就意味着每个节点都可作为根)
    那么接下来我们应该把每个根都连接起来也就是合并子问题让它形成树:
    root.left=递归(leftinorder,leftpreorder);
    root.right=递归(rightinorder,rightpreorder);
    这样问题就愉快的解决了上完整代码:

    import java.util.Arrays;
    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder==null||inorder==null||preorder.length==0||inorder.length==0){
                return null;
            }
            //生成一个根节点
            TreeNode root=new TreeNode(preorder[0]);
            int i=0;//用来记录每次中序遍历找到的根的位置
            for(;i<inorder.length;i++){
                if(inorder[i]==preorder[0]){
                    break;
                }
            }
            //创建左子树
            int[] leftPre= Arrays.copyOfRange(preorder,1,i+1);
            int[] leftIn=Arrays.copyOfRange(inorder,0,i);
            //创建右子树
            int[] rightPre= Arrays.copyOfRange(preorder,i+1,preorder.length);
            int[] rightIn=Arrays.copyOfRange(inorder,i+1,inorder.length);
            //左子树
            root.left= buildTree(leftPre,leftIn);
            //右子树
            root.right= buildTree(rightPre,rightIn);
            return root;
        }
       
    }
    

    那后序和中序呢:

    其实就是生成每层后序的规律有所差别
    然后一毛一样

    leftpostorder = [9];
    rightpostorder = [15,7,20];
    总结规律:
    leftpostorder=Arrays.copyOfRange(postorder,0,i);
    rightpostorder=Arrays.copyOfRange(postorder,i,postorder.length-1);

    是不是很好想呢。。。。。上代码

    import java.util.Arrays;
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if(inorder==null||postorder==null||inorder.length==0||postorder.length==0){
                return null;
            }
            //将后序遍历的最后一个节点取出为根
            TreeNode root=new TreeNode(postorder[postorder.length-1]);
            int i=0;//记录中序遍历根的位置
            for(;i<inorder.length;i++){
                if(postorder[postorder.length-1]==inorder[i]){
                    break;
                }
            }
            //构造左子树
            int[] leftIn=Arrays.copyOfRange(inorder,0,i);
            int[] leftPost=Arrays.copyOfRange(postorder,0,i);
            //构造右子树
            int[] rightIn=Arrays.copyOfRange(inorder,i+1,inorder.length);
            int[] rightPost=Arrays.copyOfRange(postorder,i,postorder.length-1);
            //左子树
            root.left=buildTree(leftIn,leftPost);
            //右子树
            root.right=buildTree(rightIn,rightPost);
            return root;
        }
    }
    
    展开全文
  • 我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。...

    题目描述 Description

        我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序,你却不能确定其中序遍历序列,考虑如下图中的几棵二叉树:

     

        所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。

    输入描述 Input Description

        输入文件共2行,第一行表示该树的前序遍历结果,第二行表示该树的后序遍历结果。输入的字符集合为{a-z},长度不超过26。

    输出描述 Output Description

        输出文件只包含一个不超过长整型的整数,表示可能的中序遍历序列的总数。

    样例输入 Sample Input

    abc

    cba

    样例输出 Sample Output

    4

    解题思路:

        在求解这题之前得先了解一些基础知识:

        前序遍历:根结点 ---> 左子树 ---> 右子树

        中序遍历:左子树---> 根结点 ---> 右子树

        后序遍历:左子树 ---> 右子树 ---> 根结点

        由以上的前中后遍历顺序可以看出在已知前序遍历和后序遍历的情况下,中序遍历不是唯一确定的。而且中序遍历的不确定性是由一个节点(只有一边子树)的左右子树的不确定性决定的。例如前序遍历ab,后序遍历ba,a为根,b为子树,在中序遍历中如果b为左子树,则中序遍历为ba;如果b为右子树,则中序遍历为ab。所以当这种节点有n个时,中序遍历的可能性就有:2^n;

        那么问题就转变为如果确定这种节点的数量。可以总结出一个规律,如上例。前序遍历为ab,后序遍历为ba,此时无法确定b是为左子树还是右子树,那么就产生了一个特殊节点。所以规律就是(此时a,b分别为前序遍历和后序遍历的字符串):a[i]==b[j]时,a[i+1]==b[j-1]则产生一个特殊节点

    代码如下:

    #include<stdio.h>
    
    #include<string.h>
    
    #define M 30
    
    int count=0;
    
    int power(int ans);
    
    int main()
    
    {
    
    	 char a[M],b[M];
    	
    	 int i=0,j=0;
    	 
    	 int lengthA=0,lengthB=0;
    	
    	 gets(a);
    	
    	 gets(b);
    	
    	 lengthA=strlen(a),lengthB=strlen(b);
    	
    	 for(i=0;i<lengthA;i++)
    	
    	  for(j=1;j<lengthB;j++)
    	
    	   if(a[i]==b[j]&&a[i+1]==b[j-1])
    	
    	    count++;
    	
    	 printf("%d\n",power(count));
    	 return 0;
    }
    
    int power(int ans)
    {
    	int sum=1;
    	while(--ans>=0) sum*=2;
    	return sum;
    }

     

    展开全文
  • 题目描述Description 我们都很熟悉二叉树的前序、中序、... 所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。 输入描述Input Description 输入文件共2行,第一行表示该树的前序遍历结果...

    题目描述 Description

        我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序,你却不能确定其中序遍历序列,考虑如下图中的几棵二叉树:

     

        所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。

    输入描述 Input Description

        输入文件共2行,第一行表示该树的前序遍历结果,第二行表示该树的后序遍历结果。输入的字符集合为{a-z},长度不超过26。

    输出描述 Output Description

        输出文件只包含一个不超过长整型的整数,表示可能的中序遍历序列的总数。

    样例输入 Sample Input

    abc

    cba

    样例输出 Sample Output

    4

    解题思路:

        在求解这题之前得先了解一些基础知识:

        前序遍历:根结点 ---> 左子树 ---> 右子树

        中序遍历:左子树---> 根结点 ---> 右子树

        后序遍历:左子树 ---> 右子树 ---> 根结点

        由以上的前中后遍历顺序可以看出在已知前序遍历和后序遍历的情况下,中序遍历不是唯一确定的。而且中序遍历的不确定性是由一个节点(只有一边子树)的左右子树的不确定性决定的。例如前序遍历ab,后序遍历ba,a为根,b为子树,在中序遍历中如果b为左子树,则中序遍历为ba;如果b为右子树,则中序遍历为ab。所以当这种节点有n个时,中序遍历的可能性就有:2^n;

        那么问题就转变为如果确定这种节点的数量。可以总结出一个规律,如上例。前序遍历为ab,后序遍历为ba,此时无法确定b是为左子树还是右子树,那么就产生了一个特殊节点。所以规律就是(此时a,b分别为前序遍历和后序遍历的字符串):a[i]==b[j]时,a[i+1]==b[j-1]则产生一个特殊节点

    代码如下:

    #include<stdio.h>
     
    #include<string.h>
     
    #define M 30
     
    int count=0;
     
    int power(int ans);
     
    int main()
     
    {
     
    	 char a[M],b[M];
    	
    	 int i=0,j=0;
    	 
    	 int lengthA=0,lengthB=0;
    	
    	 gets(a);
    	
    	 gets(b);
    	
    	 lengthA=strlen(a),lengthB=strlen(b);
    	
    	 for(i=0;i<lengthA;i++)
    	
    	  for(j=1;j<lengthB;j++)
    	
    	   if(a[i]==b[j]&&a[i+1]==b[j-1])
    	
    	    count++;
    	
    	 printf("%d\n",power(count));
    	 return 0;
    }
     
    int power(int ans)
    {
    	int sum=1;
    	while(--ans>=0) sum*=2;
    	return sum;
    }

     

    展开全文
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3 注意事项 你可以假设树中不存在相同数值的节点 /** * Definition of TreeNode: * class TreeNode { * public: * in...
  • 首先,在中序遍历中找到与前序遍历首元素相同的元素,然后,可以把前序遍历和中序遍历分割为四个数组,前序遍历的两个分割数组表示根结点左右子树的前序遍历中序遍历的两个分个数组表示根结点左右子树的中序遍历,...
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3 注意 你可以假设树中不存在相同数值的节点 解题 和上一题很类似的。 前序遍历:根左右 中序遍历:左根右 /** * ...
  • 由前序遍历和中序遍历重建二叉树前序序列(根-左-右):1 2 3 4 5 6中序序列(左-根-右):3 2 4 1 6 51、由前序遍历可知根节点为第一个元素1,在中序遍历序列中找到1对应位置,则1的左边就是左子树3 2 4,右边就是...
  • 前序遍历和中序遍历树构造二叉树 目录73. 前序遍历和中序遍历树构造二叉树鸣谢 73. 前序遍历和中序遍历树构造二叉树 根据前序遍历和中序遍历树构造二叉树. 你可以假设树中不存在相同数值的节点 样例 1: 输入:[]...
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3树的遍历 中序遍历:递归遍历当前节点的左子树—当前节点—右子树。 后序遍历:递归遍历当前节点的左子树—右子树—当前节点。 前序遍历:递归...
  • 先知道一个定律:从前序/后序遍历+中序遍历可以确定一棵不存在相同节点的二叉树 我们先复习一下深度优先的三个遍历: 前序遍历:根节点——左子树——右子树 中序遍历:左子树——根节点——右子树 后序遍历:左...
  • 前序遍历和中序遍历树构造二叉树 ...给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / 13 标签 二叉树 code /** * Definition of TreeNode: * class TreeNode { * public: * int v...
  • 73.前序遍历和中序遍历树构造二叉树 根据前序遍历和中序遍历树构造二叉树. 样例 样例 1: 输入:[],[] 输出:{} 解释: 二叉树为空 样例 2: 输入:[2,1,3],[1,2,3] 输出:{2,1,3} 解释: 二叉树如下 2...
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树:思路讲解: 由于是先序遍历,所以这个数组得第一个一定是其根节点,然后根据中序遍历可以将根节点得左右节点的内容得到,然后递归调用,就可以将这棵树...
  • 由前序遍历和中序遍历重建二叉树 前序序列(根-左-右):1 2 3 4 5 6 中序序列(左-根-右):3 2 4 1 6 5 1、由前序遍历可知根节点为第一个元素1,在中序遍历序列中找到1对应位置,则1的左边就是左子树324,右边...
  • 根据二叉树性质,由二叉树的前序遍历和中序遍历序,可以唯一确定一棵二叉树(设二叉树中各结点不相同)。请编写程序,根据输入的二叉树的前序遍历和中序遍历序,计算并输出其后序遍历序。 输入 输入第一行为...
  • 根据前序遍历和中序遍历树构造二叉树. 注意事项 你可以假设树中不存在相同数值...给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3思路:若前序遍历为空或者中序遍历为空则返回空; ...
  • 样例:给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3 一个前序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。 根据前序遍历的特点, 知前序序列(PreSequence)的首个...
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3思路:前序遍历的第一个节点为根节点,在中序遍历中,其左边点数为根节点的左节点,右为右节点 class Solution: """ ...
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3 假设树中不存在相同数值的节点 /** * Definition of TreeNode: * class TreeNode { * public: * int val; *
  • 给定一个二叉树,我们可以写出前序遍历中序遍历的序列,那么我们给定前序和中序遍历的序列,我们怎样才能将这颗二叉树还原呢??? 给定前序遍历的数组序列为:int[] preorder,中序遍历序列数组为:int[] inorder...
  • 所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。 输入格式 输A数据共两行,第一行表示该二叉树的前序遍历结果s1,第二行表示该二叉树的后序遍历结果s2。 输出格式 输出可能的中序遍历序列的...
  • 你可以假设树中不存在相同数值的节点样例:给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3算法要求:无解题思路:看这里算法如下: vector<int> inorder; vector<int> preorder; TreeNode *bu
  • 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / \ 1 3一刷ac。 解题思路:根据前序特点,找到跟节点,然后切分前序和中序,分别找左右跟节点。/** * Definition of TreeNode: * public class...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 373
精华内容 149
关键字:

中序遍历和前序遍历相同