精华内容
下载资源
问答
  • 根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。 分析:区间的开闭要统一,使用变动索引的方式就无需辅助空间了 #include "_myPrint.cpp" #include "stack" #include "queue" using...

    根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。

    分析:区间的开闭要统一,使用变动索引的方式就无需辅助空间了

    #include "_myPrint.cpp"
    #include "stack"
    #include "queue"
    using namespace std;
    
    // 从中序和后序遍历构造二叉树 假定二叉树中没有重复元素
    class Solution{
    public:
        TreeNode* inPost2Tree(vector<int>& in, vector<int>& post, int inBegin, int inEnd, int postBegin, int postEnd){
            // 递归写法 遵循左闭右闭的原则 使用数组索引的写法 左右索引都可以取值
    //        if (postBegin == postEnd) return NULL;
            int midValue = post[postEnd];
            TreeNode* node = new TreeNode(midValue);
            if (postBegin == postEnd) return node;
            // 找到中间元素在中序数组中的位置
            // 迭代写法 想象目前处于迭代的过程中,注意索引要在和过程中的局部索引相加
            int midIndex;
            for (midIndex = inBegin; midIndex <= inEnd; midIndex++){
                if (in[midIndex] == midValue){
                    break;
                }
            }
            // 获取新的四个索引位置
            // 中序左
            int leftinBegin = inBegin;
            int leftinEnd = midIndex - 1;
            // 中序右
            int rightinBegin = midIndex + 1;
            int rightinEnd = inEnd;
            // 后序左
            int leftpostBegin = postBegin;
            int leftpostEnd = postBegin + midIndex - inBegin - 1;
            // 后序右
            int rightpostBegin = leftpostEnd + 1;
            int rightpostEnd = postEnd - 1;
            // // log // //
            cout << "----------" << endl;
            cout << "leftInorder :";
            for (int i = leftinBegin; i <= leftinEnd; i++) {
                cout << in[i] << " ";
            }
            cout << endl;
    
            cout << "rightInorder :";
            for (int i = rightinBegin; i <= rightinEnd; i++) {
                cout << in[i] << " ";
            }
            cout << endl;
    
            cout << "leftpostorder :";
            for (int i = leftpostBegin; i <= leftpostEnd; i++) {
                cout << post[i] << " ";
            }
            cout << endl;
    
            cout << "rightpostorder :";
            for (int i = rightpostBegin; i <= rightpostEnd; i++) {
                cout << post[i] << " ";
            }
            cout << endl;
            // // log // //
            node -> left = inPost2Tree(in,post,leftinBegin,leftinEnd,leftpostBegin,leftpostEnd);
            node -> right = inPost2Tree(in, post, rightinBegin,rightinEnd,rightpostBegin,rightpostEnd);
            return node;
        }
        TreeNode* buildTree(vector<int>& in, vector<int>& post){
            if (in.size() == 0 || post.size() == 0) return NULL;
            // 左闭右闭
            return inPost2Tree(in,post,0,in.size()-1,0,post.size()-1);
        }
    
    };
    
    int main(){
        Solution s;
        vector<int> in = {1,2,3,4,5};
        vector<int> post = {1,3,2,5,4};
        TreeNode* root  = s.buildTree(in,post);
        printCollection p;
        p.printTreeLevelOrder(root);
    
    }
    
    
    展开全文
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 //中序遍历 inorder = [9,3,15,20,7] //后序遍历 postorder = [9,15,7,20,3] //返回如下的二叉树: // 3 // / \ // ...

    题目要求

    根据一棵树的中序遍历与后序遍历构造二叉树。
    注意: 你可以假设树中没有重复的元素。

    例如,给出

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

    代码

        private int index2;
        public TreeNode buildTree(int[] preorder, int[] postorder) {
            index2 = 0;
            //先逆置
            int length = postorder.length;
            for (int i = 0; i < length / 2; i++) {
                int temp = postorder[i];
                postorder[i] = postorder[length - 1 - i];
                postorder[length - 1 - i] = temp;
            }
            return buildTreeHelper(preorder,postorder,0,postorder.length);
        }
    
        private TreeNode buildTreeHelper(int[] preorder, int[] postorder, int left, int right) {
            if (left >= right){
                //中序遍历结果为空,这个数就是空树
                return null;
            }
            if (index2 >= preorder.length){
                return null;
            }
            TreeNode root = new TreeNode((char) preorder[index2]);
            index2++;
            int pos = find(postorder,left,right,root.val);
            root.right = buildTreeHelper(preorder,postorder,pos+1,right);
            root.left = buildTreeHelper(preorder,postorder,left,pos);
    
            //一个树的先序遍历的镜像和后序遍历的逆置相同,,,,根右左
            //所以先逆置后序遍历,再调整左右根的打印位置
    
            return root;
        }
    
        private int find(int[] inorder, int left, int right, int toFind) {
            for (int i = left; i < right; i++){
                if (inorder[i] == toFind){
                    return i;
                }
            }
            return -1;
        }
    
    展开全文
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 用例描述: 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / 9 20 / 15 7 ...

    题目描述

    根据一棵树的中序遍历与后序遍历构造二叉树。
    注意:
    你可以假设树中没有重复的元素。

    用例描述:

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

    思路

    1. 题目将中序遍历和后序遍历的结果以数组形式给出,不便于操作,因此可以用集合类来辅助完成二叉树的构建,这里我选用的是常用的list
    2. 如果中序遍历的list长度为0,说明是空树直接返回nul
    3. 如果中序遍历的list长度为1,说明当前节点是叶子节点,直接返回
    4. 根据后序遍历的list,取到最后一个元素就是根节点
    5. 根据中序遍历取到的第一个元素就是左子树位置记作leftsize
    6. 根据中序遍历结果,可将其分为:
      leftIn [0,leftSize) ; rightIn [ leftSize+1,inOrderList.size() )
    7. 根据后序遍历结果,可将其分为:
      leftPost [0,leftSize) ; rightPost [ leftSize,postOrderList.size()-1);

    代码如下:

    import java.util.ArrayList;
    import java.util.List;
    
    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int val) {
            this.val = val;
        }
    }
    class Solution {
        private List<Integer> arrayToList(int[] arr){
            List<Integer> list = new ArrayList<>();
            for (int x : arr){
                list.add(x);
            }
            return list;
        }
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            //1.将数组转化为list
            List<Integer> inOrderList = arrayToList(inorder);
            List<Integer> postOrderList = arrayToList(postorder);
            //2.构建辅助方法
            return buildHelper(inOrderList,postOrderList);
        }
    
        private TreeNode buildHelper(List<Integer> inOrderList, List<Integer> postOrderList) {
            //如果inOrderList.size() == 0,说明为空树,直接返回null
            if (inOrderList.size() == 0){
                return null;
            }
            //如果inOrderList.size() == 1,说明当前树只有一个节点,直接返回该节点即可
            if (inOrderList.size() == 1){
                return new TreeNode(inOrderList.get(0));
            }
            //postOrderLise.get(postOrderList.size()-1)表示根节点的值
            int rootVal = postOrderList.get(postOrderList.size()-1);
            TreeNode root = new TreeNode(rootVal);
            //根据rootVal在中序遍历中确定左子树的位置
            int leftSize = inOrderList.indexOf(rootVal);
            List<Integer> leftIn = inOrderList.subList(0,leftSize);
            List<Integer> rightIn = inOrderList.subList(leftSize+1,inOrderList.size());
            List<Integer> leftPost = postOrderList.subList(0,leftSize);
            List<Integer> rightPost = postOrderList.subList(leftSize,postOrderList.size()-1);
            //递归创建左子树
            root.left = buildHelper(leftIn,leftPost);
            //递归创建右子树
            root.right = buildHelper(rightIn,rightPost);
            return root;
        }
    }
    
    展开全文
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: class Solution { ...

    根据一棵树的前序遍历与中序遍历构造二叉树。
    注意:你可以假设树中没有重复的元素。
    例如,给出
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树:
    在这里插入图片描述
    在这里插入图片描述

    class Solution {
        public int preIndex = 0;
        //preIndex遍历前序数组的标记
        public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
            //说明没有左树 或者没有右树
            if(inbegin > inend) {
                return null;
            }
           TreeNode root = new TreeNode(preorder[preIndex]);
            //在中序遍历的数组当中  找到当前跟节点所在的位置
            //index当前跟节点所在的位置
            int index = findValInorder(inorder,preorder[preIndex],inbegin,inend);
            preIndex++;
            root.left = buildTreeChild(preorder,inorder,inbegin,index-1);
            root.right = buildTreeChild(preorder,inorder,index+1,inend);
            return root;
        }
      //findValInorder找到当前节点在中序遍历的数组当中的位置
        public int findValInorder(int[] inorder,int key,int inbegin,int inend) {
            for(int i = inbegin;i <= inend; i++) {
                if(inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder == null || inorder == null) return null;
            if(preorder.length == 0|| inorder.length == 0) return null;
    
            return buildTreeChild(preorder,inorder,0,inorder.length-1);
        }
    
    }
    

    力扣真题

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

    class Solution {
        public int preIndex =0;
        public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inbegin,int inend) {
            //说明没有左树 或者没有右树
            if(inbegin > inend) {
                return null;
            }
            TreeNode root = new TreeNode(postorder[preIndex]);
            //在中序遍历的数组当中  找到当前跟节点所在的位置
            int index = findValInorder(inorder,postorder[preIndex],inbegin,inend);
            preIndex--;
            root.right = buildTreeChild(inorder,postorder,index+1,inend);
            root.left = buildTreeChild(inorder,postorder,inbegin,index-1);
            return root;
        }
    
        public int findValInorder(int[] inorder,int key,int inbegin,int inend) {
            for(int i = inbegin;i <= inend; i++) {
                if(inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if(postorder == null || inorder == null) return null;
            if(postorder.length == 0|| inorder.length == 0) return null;
             preIndex =postorder.length-1;
            return buildTreeChild(inorder,postorder,0,inorder.length-1);
        }
    
    }
    

    力扣真题

    展开全文
  • C++ 二叉树 前序遍历 中序遍历 后序遍历 通过递归代码推出非递归实现 通过遍历规则推出非递归实现
  • 题目1078:二叉树遍历题目描述:二叉树的前序、中序、后序遍历的定义:前序...给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。输入:两个字符串,其长度...
  • /*分别使用递归思想迭代思想实现二叉树的前序遍历、中序遍历后序遍历*/ //递归思想实现前序遍历、中序遍历后序遍历 //1、递归思想实现前序遍历 void PreOrderTraverse(BitTree T) { if (T == NULL) return; ...
  • 可以跟之前这篇形成对比http://blog.csdn.net/hhooong/article/details/43195395代码如下:#include#includeusing namespace std ;struct BinTreeNode {char data ;BinTreeNode *left ;BinTreeNode *right ;...
  • 二叉树的概念 1、每个节点最多只有两个子节点的树称为二叉树 2、二叉树的子节点分为左节点和右节点 3、如果二叉树的所有节点都在最后一层,并且节点总数为2^n-1,n为...后序遍历:先遍历左子树,再遍历右子树,最后输出
  • 二叉树按照从左到右的规则,把六种遍历简化到只研究三种遍历:前序遍历(DLR),中序遍历(LDR),后序遍历(LRD)。 二叉树遍历的实质是递归。 目录 二叉树的遍历 前序遍历 中序遍历 后序遍历 练习写出下列...
  • 二叉树的先序,中序,后序如何遍历,不在此多说了。...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。输入:输入可能包含多个测试样例,对于每个...
  • 那么对下图而言,前序遍历为UNI,中序遍历为NUI,后序遍历为NIU,观察这三种情况,可以发现前中后实际上指的是根的遍历顺序。 实例 假设给定如下所示一颗二叉搜索树,那么我们如何对其进行前序遍历、中序遍历以及...
  • void pre_order(TreeNode * Node)//前序遍历递归算法 { if(Node == NULL) return; printf("%d “, Node->data);//显示节点数据,可以更改为其他操作。在前面 pre_order(Node->left); pre_orde
  • 实验目的编写一个程序,实现二叉树的先序遍历,中序遍历后序遍历。实验内容编程序并上机调试运行。编写一个程序,实现二叉树的先序遍历,中序遍历后序遍历。编写程序/***********二叉树的遍历**************/#...
  • 一、二叉树的遍历概念 二叉树的遍历是指从根结点触发,按照某种次序依次访问二叉树中所有结点,...中序遍历:若二叉树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然
  • 绝对要收藏【数据结构之树】一、基础概念二、前序遍历2.1 递归参考代码2.2 非递归参考代码 一、基础概念 树 :由n个有限节点组成的一个具有层次关系的集合; 根节点 :没有父节点的节点; 二、前序遍历 遍历顺序...
  • 刚刚又 复习 预习了一下树的遍历,也刚好再看看每两种遍历方法组合后建立树的...1、已知前序遍历、中序遍历后序遍历 解题思想: 前序遍历中,根节点一定是会出现在最前面,我们就可以通过这个点来得到每个子树的根
  • 链式存储结构存储的递归思想遍历二叉树之前讲过,树是由根结点和子树部分...遍历左子树,之后访问根结点,然后遍历右子树,称为“中序遍历”;遍历完左右子树,再访问根结点,称为“后序遍历”。三种方式唯一的不同...
  • 本文主要讲解如何根据二叉树的中序遍历后序遍历,构建树。 在写PTA的钻石争霸赛时,在写最后一道题时,刚开始需要根据二叉树的中序遍历后序遍历,构建二叉树,然后才能继续写题。经过当时向学长学习之后,也完成...
  • 2,由中序遍历知BDCE为左子树,FHG为右子树 3,再由后序遍历知DECB中B为根节点,HGF中F为根节点 4,再由中序遍历知BDCE中的DCE为B的右子树,同理HG为F的右子树 5,由后序遍历知DEC中C为根节点,HG中G为根节点 6,由...
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / 9 20 / 15 7 从...
  • 用递归方法实现二叉树的中序遍历后序遍历算法 //用递归方法实现二叉树的中序遍历后序遍历算法; #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char ...
  • 填空题:已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为_____________。  答案:DGEBHFCA。  解题过程:  一、基本概念扫盲:对一棵二叉树进行遍历,我们可以采取3中顺序...
  • 1.前序遍历 对于当前节点,先输出该节点,然后输出他的左孩子,最后输出他的右孩子。以上图为例,递归的过程如下: (1):输出 1,接着左孩子; (2):输出 2,接着左孩子; (3):输出 4,左孩子为空,再接着右...
  • 图6.1.13应输出的后序遍历序列为ACBMXZPD注意:你的程序应能鉴别任何的错误输入。题解1鉴别错误输入设predstr—前序串;s1—前序串的字符集;midstr—中序串;s2—中序串的字符集;predstr串midstr串必须同时满足...
  • /*** 给出先序遍历和中序遍历序列求出二叉树的后续遍历序列* @author wxisme**/public class ToReverse {public static void main(String[] args) {Scanner scan = new Scanner(System.in);Stri...
  • // 再后序遍历右子树 Visit(T->data); // 最后访问根结点 } } void main() { BiTree T; InitBiTree(T); // 初始化二叉树T printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n")...
  • 对二叉树的前中后序递归以及非递归算法以及层序遍历思想做了整合 因为某些书籍上对这类算法,写的非常笼统,所以,这里将从树的链式存储开始,结合整个 链表、栈、队列等结构来完成对树的学习,当然,这里也将会完美...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 79,122
精华内容 31,648
关键字:

中序遍历与后序遍历