精华内容
下载资源
问答
  • 在leetcode上两题,分别是根据前序/后序 和中序遍历重构二叉树。思路都是一样的,但是要记住,在从后序遍历重构二叉树的时候,要先从右子进行建立,因为后序遍历先遍历的是右子。 前序遍历+中序遍历 (1)首先...

    在leetcode上有两题,分别是根据前序/后序 和中序遍历重构二叉树。思路都是一样的,但是要记住,在从后序遍历重构二叉树的时候,要先从右子树进行建立,因为后序遍历先遍历的是右子树。

    前序遍历+中序遍历

    (1)首先进行边界判断,如果遍历数组为0或者1的情况下,说明这个树只有一个顶点或者没有顶点,直接进行构造。
    (2)根据前序遍历和中序遍历建立二叉树的思路是:前序遍历依次每一个节点对应一个子树,这个节点在中序遍历中找到它相应的位置,它的左边(当然是在子树数组范围内)就是左子树的顶点,右边就是右子树的顶点。

    前序遍历就是确定树的根节点,中序遍历就是确定树的左右子树。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        int preIndex = 0;
        int[] preorder;
        int[] inorder;
        Map<Integer, Integer> map = new HashMap<>();
    
    
    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
    
            if(preorder.length == 0)
                return null;
            if(preorder.length == 1)
                return new TreeNode(preorder[0]);
    
            this.preorder = preorder;
            this.inorder =  inorder;
    
            int len = inorder.length;
            for(int i = 0; i < len; i++){
                map.put(inorder[i], i);
            }
    
    
            TreeNode res = func(0, len-1);
            return res;
            
        }
    
        public TreeNode func(int l, int r){
            if(l > r)
                return null;
            
            TreeNode root = new TreeNode(preorder[preIndex]);
            int inIndex = map.get(preorder[preIndex]);
            preIndex++;
    
            root.left = func(l, inIndex-1);
            root.right =  func(inIndex+1, r);
    
            return root;
        }
    }
    
    

    后序遍历+中序遍历

    代码相同,注意的是需要先构建右子树。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
    
        Map<Integer, Integer> map;
        int postIndex;
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int len = inorder.length;
            if(len == 0)
                return null;
            if(len == 1)
                return new TreeNode(inorder[0]);
            map = new HashMap<>();
            postIndex = len-1;
            for(int i = 0; i < len; i++)
            {
                map.put(inorder[i], i);
            }
    
            TreeNode res = fuc(0, len-1, inorder, postorder);
            return res;
    
    
        }
    
        public TreeNode fuc(int l, int r, int[] inorder, int[] postorder){
            if(l > r)
                return null;
    
            TreeNode newNode = new TreeNode(postorder[postIndex]);
            System.out.println(newNode.val);
            int inIndex = map.get(postorder[postIndex]);
            postIndex--;
            
            newNode.right = fuc(inIndex+1, r, inorder, postorder);
            newNode.left = fuc(l, inIndex-1, inorder, postorder);
    
            return newNode;
            
        }
    }
    
    展开全文
  • 根据一棵中序遍历与后序遍历构造二叉树题目思路分析参考代码 题目 注意: 你可以假设没有重复的元素。 例如,给出: 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树...

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

    题目

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

    例如,给出:
    中序遍历 inorder = [9,3,15,20,7]
    后序遍历 postorder = [9,15,7,20,3]

    返回如下的二叉树:
    在这里插入图片描述

    思路分析

    二叉树相关的很多问题的解决思路都有分治法的思想在里面。
    复习一下分治法的思想:把原问题分解(Divide)成若干个与原问题结构相同但规模更小的子问题,待子问题解决(Conquer)以后,再合并(Combine)它们,原问题就得以解决。
    在这里插入图片描述
    用一个普遍的例子进行具体理解:
    在这里插入图片描述

    参考代码

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
            val = x;
        }
    }
    
    public class Solution {
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int inLen = inorder.length;
            int postLen = postorder.length;
            
            if (inLen != postLen) {
                throw new RuntimeException("输入错误");
            }
            return buildTree(inorder, 0, inLen - 1, postorder, 0, postLen - 1);
        }
        
        /**
         * 使用中序遍历序列 inorder 的子区间 [inLeft, inRight]
         * 与后序遍历序列 postorder 的子区间 [postLeft, postRight] 构建二叉树
         *
         * @param inorder   中序遍历序列
         * @param inLeft    中序遍历序列的左边界
         * @param inRight   中序遍历序列的右边界
         * @param postorder 后序遍历序列
         * @param postLeft  后序遍历序列的左边界
         * @param postRight 后序遍历序列的右边界
         * @return 二叉树的根结点
         */
         
        private TreeNode buildTree(int[] inorder, int inLeft, int inRight,
                                   int[] postorder, int postLeft, int postRight) {
            if (inLeft > inRight || postLeft > postRight) {
                return null;
            }
    
            int pivot = postorder[postRight];
            int pivotIndex = inLeft;
    
            while (inorder[pivotIndex] != pivot) {
                pivotIndex++;
            }
            TreeNode root = new TreeNode(pivot);
            root.left = buildTree(inorder, inLeft, pivotIndex - 1,
                    postorder, postLeft, postRight - inRight + pivotIndex - 1);
    
            root.right = buildTree(inorder, pivotIndex + 1, inRight,
                    postorder, postRight - inRight + pivotIndex, postRight - 1);
            return root;
        }
    }
    
    展开全文
  • 根据一棵的前序遍历与中序遍历构造二叉树。 注意: 你可以假设没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 题解:首先是递归解决。依次遍历前序顺序作为...

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

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

    例如,给出

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

    题解:首先是递归解决。依次遍历前序顺序作为父节点,然后在中序遍历中一定范围内(a)找到对应的所在位置(inex),在范围a中,index之前是该节点的左子树节点,index之后是该节点的右子树节点。如此反复,则构建成功。注意:范围a要有,没有则结束。
    代码:

    class Solution {
        int index = 0;
    
        public TreeNode buildTree1(int[] preorder, int[] inorder, int ibegin, int iend) {
            if (iend < ibegin)
                return null;
            int inorderIndex = getIndex(inorder, ibegin, iend, preorder[index]);
            TreeNode current = new TreeNode(preorder[index]);
            index++;
            current.left = buildTree1(preorder, inorder, ibegin, inorderIndex - 1);
            current.right = buildTree1(preorder, inorder, inorderIndex + 1, iend);
            return current;
        }
    
        public int getIndex(int[] inorder, int ibegin, int iend, int val) {
            for (int i = ibegin; i <= iend; i++)
                if (inorder[i] == val)
                    return i;
            return -1;
        }
    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0)
                return null;
            return buildTree1(preorder, inorder, 0, inorder.length - 1);
        }
    }
    

    扩展:那如果给一个中序和后序遍历的怎么办呢?其实和前者的思想相似,但是不同的是,首先我们依次遍历后续遍历的结果(倒序遍历后续结果)。
    代码:

    class Solution {
        int index;
    
        public TreeNode buildTree1(int[] preorder, int[] inorder, int ibegin, int iend) {
            if (iend < ibegin)
                return null;
            int inorderIndex = getIndex(inorder, ibegin, iend, preorder[index]);
            TreeNode current = new TreeNode(preorder[index]);
            index--;
            current.right = buildTree1(preorder, inorder, inorderIndex + 1, iend);
            current.left = buildTree1(preorder, inorder, ibegin, inorderIndex - 1);
    
            return current;
        }
    
        public int getIndex(int[] inorder, int ibegin, int iend, int val) {
            for (int i = ibegin; i <= iend; i++)
                if (inorder[i] == val)
                    return i;
            return -1;
        }
    
        public TreeNode buildTree(int[] inorder, int[] preorder) {
            if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0)
                return null;
            index = inorder.length - 1;
            return buildTree1(preorder, inorder, 0, inorder.length - 1);
        }
    }
    
    展开全文
  • 现在网上很多关于二叉树的遍历,CSDN里面也很多,但是我自己在学习的时候发现很多或多或少有点小问题,我不敢保证我的没有问题,的话,请大神指教。 二叉树遍历: 1.先序遍历 根节点->左子树->右子 ...

    关于二叉树遍历问题:先序遍历,中序遍历,后序遍历
    现在网上有很多关于二叉树的遍历,CSDN里面也有很多,但是我自己在学习的时候发现很多或多或少有点小问题,我不敢保证我的没有问题,有的话,请大神指教。
    二叉树遍历:
    1.先序遍历 根节点->左子树->右子树
    2.中序遍历 左子树->根节点->右子树
    3.后序遍历 根节点->左子树->右子树
    我觉得学习这个遍历题,对这个“根节点”不要理解得很单一,认为是一个节点,只要是有子节点的你都可以认为它是”根节点“。你把这句话理解一下,我放张图你去揣摩一下,肯定就理解了。

    这张图是浙江大学公开课我截的图,应该是不可能存在问题的
    

    在这里插入图片描述

    展开全文
  • 中序遍历有个特点 根节点的左侧是左子树节点,右侧是右子节点。 依靠前序遍历和中序遍历的特点构建二叉树 leetcode 105 根据一棵的前序遍历与中序遍历构造二叉树。 注意: 你可以假设没有重复的元素。 例如...
  • 假设现在某二叉树的先序遍历和中序遍历,我们应该如何建树? 基本思路: 分别求得根节点的左子树和右子的先序遍历序列与中序遍历序列 分别以左子树和右子为新进行第一步操作 直至没有子树为止 那么我们...
  • Morris 中序遍历 用 Morris 中序遍历的方法把中序遍历的空间复杂度优化到 O(1) Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点,并且 Morris 中序遍历寻找下一个点始终是通过转移到 \rm rightright ...
  • 中序遍历的几种情况: 分析1:什么时候访问根,什么时候访问左子树,什么访问右子。 当左子树为空或左子树已经访问完毕以后,再访问根。 访问完毕根以后,再访问右子。 分析2:为什么是栈,而不是其他(比如...
  • 什么叫前序、后序、中序? 一棵二叉树由根结点、左子树和右子三部分组成,若规定 D、L...LDR–中序遍历(根在中,从左往右,一棵的左子树永远在根前面,根永远在右子前面) LRD–后序遍历(根在后,从左往右,一
  • 的非递归中序遍历

    2018-04-30 18:15:57
    如果结点没有右子(结点访问完毕),回退,让栈顶元素出栈,访问栈顶元素,并访问右子,重复步骤1如果栈为空,表示遍历结束。#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &...
  • 二叉树的链式存储及实现 1、的概念及结构 1.1、的结构 ...没有父结点的结点称为根结点; 每一个非根结点且只有一个父结点; 每个子结点可以分为多个不相交的子树。 1.2、的表示 的表示...
  • 注:题目源自leetcode105&...根据一棵的前序遍历与中序遍历构造二叉树。注意: 你可以假设没有重复的元素。 例如,给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: .
  • 文章目录从前序与中序遍历序列构造二叉树从中序...根据一棵的前序遍历与中序遍历构造二叉树。当然也是力扣105的原题。 注意:你可以假设没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历
  • 问题描述 根据一棵的前序遍历与中序遍历构造二叉树。 注意: 你可以假设没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7...前序与中序遍历的序列一个特点: 对于某棵来讲,先序遍历的序列的...
  • 综合以上特点,我们就想有没有一种结构,能够删除、查找、插入都不是那么困难,能够综合上述优 点,这个时候我们就引入了二叉排序结构查找是将查找表按照某种规律建成结构。因为建构的结构是按某种规律...
  • 构造二叉树从前序与中序遍历序列构造二叉树从中序与后序遍历序列构造二叉树非递归 从前序与中序遍历序列构造二叉树 采用递归创建: 1.对于参数preorder,采用引用的方式创建,保证共用一个 2.startidx和endidx直接...
  • 如果结点没有右子(结点访问完毕),回退,让栈顶元素出栈,访问栈顶元素,并访问右子,重复步骤1 如果栈为空,表示遍历结束。 #include "iostream" #include "stack" using namespace std;...
  • 中序遍历右子中序遍历所看到的第一个节点 D是第一个节点,没有左儿子,可能右儿子,先遍历D的右儿子,没有右儿子,回到D的父亲B。 遍历B的右子E级所在的,从E一直往左走 G的下一个结点是E(E的左...
  • 根据一棵的前序遍历与中序遍历构造二叉树。 注意: 你可以假设没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15...
  • 如果一个节点右子,那么中序遍历的下个节点就是它的右子中最左子结点。  2.如果一个节点没有右子,且它是它父节点的左子结点,那么中序遍历的下个节点就是它的父节点。  3.如果一个节点没有右子,且它是...
  • 也就是说,当前结点有没有左子树对该问题没有影响,因为,中序遍历的下一个结点一定不可能在左子树中,所以我们主要关注当前结点有没有右子。 1)当前结点有右子,那么下一个结点一定在右...
  • 根据一棵的前序遍历与中序遍历构造二叉树。 注意: 你可以假设没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15 ...
  • 中序遍历性质,找下一节点与右节点有关,即右子。 当右子,下个结点就是右子最左边的左节点。 当没有右子,可以分成两类 1. 当前节点是父节点左孩子,则父节点就是下一个节点 2. 当前节点是父节点的...
  • 1) 一个特殊的节点,成为根节点,根节点没有前驱节点 2)除根节点外,其余节点被分为n个互不相交的集合,每个集合又类似一个 3)是递归定义的 概念 节点的度:一个节点含有的子树的个数称为该节点的度 的度...
  • 前序(根左右):针对一个结点,首先进行遍历输出,然后判断是否左子树,如果左子树,对其左子树进行前序遍历,再判断是否右子,如果右子,对右子进行遍历,如果既没有左子树,也没有右子,则进行...
  • 说到底的本质和链表没有太大区别,只是了分支,学习过数据结构的同学都知道,构建一棵往往使用递归的思想,而前序遍历和中序遍历就是以不同的顺序对进行深度优先搜索。利用遍历的结果来重构一棵,也是中...
  • 根据一棵的前序遍历与中序遍历构造二叉树。 注意: 你可以假设没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15 ...
  • 94. 二叉树的中序遍历 难度中等 给定一个二叉树,返回它的中序 遍历。 示例: 进阶: 递归算法很简单,你可以通过迭代算法完成吗? 思路1.0: 利用栈,当前节点没有左子树时,打印nodeNow->val;左子树时,压入...
  • 中序遍历 先走到的后访问,后走到的先访问,采用栈结构。 步骤: 1.如果节点左子树,该节点入栈,否则访问该节点。 2.如果节点右子,重复步骤1。 3.如果节点没有右子,访问完毕,根据栈顶指示退回,访问...
  • 根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅一个节点,值为a. ②输入123213则返回的指针指向...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 957
精华内容 382
关键字:

树有没有中序遍历