精华内容
下载资源
问答
  • 概述在上一篇文章中讲到顺序存储二叉树,一般是用于完全二叉树,通过统一的数学公式可以将数组还原成完全二叉树而对于普通的二叉树来说,也可以根据前序、中序和后序遍历得到的数组,还原二叉树还原还原的情况分两种...

    概述在上一篇文章中讲到顺序存储二叉树,一般是用于完全二叉树,通过统一的数学公式可以将数组还原成完全二叉树

    而对于普通的二叉树来说,也可以根据前序、中序和后序遍历得到的数组,还原二叉树

    还原还原的情况分两种,分别是根据前序、中序和根据中序、后序

    采用的二叉树如下图所示:d2c54f9b3904e26c3527374dedb68300.png

    注意:前序和后序是没有办法还原二叉树

    根据前序、中序还原二叉树如下图所示:92afe7fb468b55d589b1427e2b727869.png

    基本思路:根据前序数组,我们能够确定根节点(因为前序数组的根节点一定是第一个)

    中序数组根据根节点能够确定左右子树的位置。(因为中序数组的根节点一定能够分开左右子树)

    前序数组根据中序数组的左右子树的位置,也能够确定自己根节点的左右子树的位置(这部分可以看看代码怎么写的)

    然后再分别递归左子树的前序、中序以及右子树的前序、中序,直到最后左右子树的长度都为0

    代码如下:/**

    * * @param pre 前序数组

    * @param middle 中序数组

    * @return 返回根节点

    */

    public static TreeNode buildTree(int[] pre, int[] middle){

    if (pre == null || middle == null || pre.length == 0 || middle.length == 0 || pre.length != middle.length)

    return null;

    //首先找到根节点

    TreeNode root = new TreeNode(pre[0]);

    //根据根节点的值找到中序遍历中的根节点的位置索引

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到前序和中序中的左子树

    //copyOfRange:拷贝[from, to)区间里的数据,左闭右开

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftPre = Arrays.copyOfRange(pre, 1, rootIndex + 1);

    //找到前序和中序中的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middle.length);

    int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);

    //用递归再次构建左右子树

    TreeNode left = buildTree(leftPre, leftMiddle);

    TreeNode right = buildTree(rightPre, rightMiddle);

    //将左右子树添加到根节点上

    root.left = left;

    root.right = right;

    return root;

    }

    根据中序、后序还原二叉树根据中序、后序和根据前序、中序是一样的道理,只不过是根节点从前序的第一个变为后序的最后一个,如下图所示:eb4c0c70ee21f1b777eddcdcae4f875e.png

    代码如下://根据中序和后序还原二叉树

    /**

    * * @param middle 中序数组

    * @param last 后序数组

    * @return 根节点

    */

    public static TreeNode buildTree2(int[] middle, int[] last){

    if (middle == null || last == null) return null;

    int middleLen = middle.length; //获取中序数组的长度

    int lastLen = last.length; //获取后序数组的长度

    if (middleLen == 0 || lastLen == 0) return null;

    //首先根据后序获取根节点

    TreeNode root = new TreeNode(last[lastLen - 1]);

    //根据root获取中序的根节点的索引值

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到中序和后序的左子树

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftLast = Arrays.copyOfRange(last, 0, rootIndex);

    //找到中序和后序的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middleLen);

    int[] rightLast = Arrays.copyOfRange(last, rootIndex, lastLen - 1);

    //用递归再次构建左子树和右子树

    TreeNode left = buildTree2(leftMiddle, leftLast);

    TreeNode right = buildTree2(rightMiddle, rightLast);

    //将左右子树添加到根节点

    root.left = left;

    root.right = right;

    return root;

    }

    总体代码//树节点:

    public class TreeNode {

    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int val){

    this.val = val;

    }

    }

    //还原代码:

    public class Travel {

    public static void preorder_Traversal(TreeNode node){

    if (node == null)

    return;

    System.out.println(node.val);

    preorder_Traversal(node.left);

    preorder_Traversal(node.right);

    }

    public static void inorder_Traversal(TreeNode node, int val){

    if (node == null)

    return;

    inorder_Traversal(node.left, val);

    System.out.println("---" + node.val);

    if (node.val == val){

    System.out.println("找到了:" + node.val);

    return ; }

    inorder_Traversal(node.right, val);

    }

    public static void postorder_Traversal(TreeNode node){

    if (node == null)

    return;

    postorder_Traversal(node.left);

    postorder_Traversal(node.right);

    System.out.println(node.val);

    }

    public static int getIndex(int[] arr, int target){

    for (int i = 0; i < arr.length; i ++){

    if (arr[i] == target){

    return i;

    }

    }

    return -1;

    }

    //根据前序和中序还原二叉树

    /**

    * * @param pre 前序数组

    * @param middle 中序数组

    * @return 返回根节点

    */

    public static TreeNode buildTree(int[] pre, int[] middle){

    if (pre == null || middle == null || pre.length == 0 || middle.length == 0 || pre.length != middle.length)

    return null;

    //首先找到根节点

    TreeNode root = new TreeNode(pre[0]);

    //根据根节点的值找到中序遍历中的根节点的位置索引

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到前序和中序中的左子树

    //copyOfRange:拷贝[from, to)区间里的数据,左闭右开

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftPre = Arrays.copyOfRange(pre, 1, rootIndex + 1);

    //找到前序和中序中的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middle.length);

    int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);

    //用递归再次构建左右子树

    TreeNode left = buildTree(leftPre, leftMiddle);

    TreeNode right = buildTree(rightPre, rightMiddle);

    //将左右子树添加到根节点上

    root.left = left;

    root.right = right;

    return root;

    }

    //根据中序和后序还原二叉树

    /**

    * * @param middle 中序数组

    * @param last 后序数组

    * @return 根节点

    */

    public static TreeNode buildTree2(int[] middle, int[] last){

    if (middle == null || last == null) return null;

    int middleLen = middle.length; //获取中序数组的长度

    int lastLen = last.length; //获取后序数组的长度

    if (middleLen == 0 || lastLen == 0) return null;

    //首先根据后序获取根节点

    TreeNode root = new TreeNode(last[lastLen - 1]);

    //根据root获取中序的根节点的索引值

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到中序和后序的左子树

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftLast = Arrays.copyOfRange(last, 0, rootIndex);

    //找到中序和后序的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middleLen);

    int[] rightLast = Arrays.copyOfRange(last, rootIndex, lastLen - 1);

    //用递归再次构建左子树和右子树

    TreeNode left = buildTree2(leftMiddle, leftLast);

    TreeNode right = buildTree2(rightMiddle, rightLast);

    //将左右子树添加到根节点

    root.left = left;

    root.right = right;

    return root;

    }

    public static void main(String[] args) {

    //前序、中序测试

    // int[] pre = {18, 20, 16, 29, 39, 8};

    // int[] middle = {16, 20, 39, 8, 29, 18};

    //

    // TreeNode root = buildTree(pre, middle);

    // preorder_Traversal(root);

    //中序、后序测试

    int[] middle = {16, 20, 18, 39, 29, 8};

    int[] last = {16, 20, 39, 8, 29, 18};

    TreeNode node = buildTree2(middle, last);

    preorder_Traversal(node);

    }

    }

    展开全文
  • 依靠中序遍历数组和后序遍历数组可以唯一确定一棵二叉树; 但是,依靠前序遍历数组和后序遍历数组无法唯一确定一棵二叉树; 从前序与中序遍历序列构造二叉树 根据一棵树的前序遍历与中序遍历构造二叉树。当然也是...

    遇到二叉树相关的问题,多半和递归有关系,二叉树遍历也是递归遍历(从树得到序列),二叉树的构建也是递归构建(从序列得到一个二叉树)

    依靠前序遍历数组和中序遍历数组可以唯一确定一棵二叉树;
    依靠中序遍历数组和后序遍历数组可以唯一确定一棵二叉树;
    但是,依靠前序遍历数组和后序遍历数组无法唯一确定一棵二叉树;

    从前序与中序遍历序列构造二叉树

    根据一棵树的前序遍历与中序遍历构造二叉树。当然也是力扣105的原题。

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

    例如,给出

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

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7
    

    分析:

    给定一个前序序列和一个中序序列,且里面没有重复的元素,如何构造一和二叉树呢?我们可以先单独观察两个序列的特征:

    前序遍历:遍历规则为(根,[左侧区域],[右侧区域])。
    中序遍历:遍历规则为([左侧区域],根,[右侧区域])。

    其中前序遍历的左侧区域和中序遍历的左侧区域包含元素的范围相同,根也是相同的。所以可以进行这样的操作:

    1. 根据前序遍历的第一个找到根节点,可以确定根。
    2. 通过中序遍历找到根节点的值,这样可以知道左侧区域和右侧区域节点个数多少。
    3. 根节点左侧区域由前中序列确定的左侧区域确定,根节点的右侧节点由前中序序列的右侧区域确定。

    具体的实现上,可以使用一个HashMap存储中序存储的序列,避免重复计算。实现的代码为:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {   // leecode给你提供一个二叉树类给你用
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
       public TreeNode buildTree(int[] preorder, int[] inorder) {
    		if(preorder.length==0)
    			return null;
    		TreeNode root=new TreeNode(preorder[0]);
    		Map<Integer, Integer>map=new HashMap<Integer, Integer>();
    		for(int i=0;i<inorder.length;i++)
    		{
    // 为什么要把中序遍历的整个数组放到map中,
    // 因为前序序列中确定的根节点要在中序序列中确定位置,
    // 然后确定左右子树,所以需要将数组变为map,
    			map.put(inorder[i], i);
    		}
    		// 六个参数,preorder三个,inorder三个
    		return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);
        }
    
    	private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> map, int inStart, int inEnd) {		
    		if(preEnd<preStart||inEnd<inStart)
    			return null;
    		TreeNode node=new TreeNode(preorder[preStart]);  // 拿着前序遍历数组的第一个元素,新建一个二叉树根结点,这个根节点是作为返回值的
    		int i=map.get(preorder[preStart]);// 每次前序序列确定的根节点在中序遍历中的位置i,然后分割左右子树
    		
    		int leftlen=i-inStart;// i-inStart变为中序遍历左边的长度,即左子树长度
    		//六个参数,前序遍历三个,中序遍历三个,继续构造左子树
    		node.left=buildTree(preorder, preStart+1, preStart+leftlen, map, inStart, i-1);
    		//六个参数,前序遍历三个,中序遍历三个,继续构造右子树
    		node.right=buildTree(preorder, preStart+leftlen+1,preEnd, map, i+1, inEnd);
    		return node;		
    	}
    }
    

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

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7
    

    解释左子树:node.left=buildTree(preorder, preStart+1, preStart+1+leftlen, map, inStart, i-1);
    之前是 return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);

    前序序列启始点:为什么之前是preStart=0,现在是preStart+1?因为去掉一个根节点,good

    前序序列终点:为什么之前是preorder.length-1,现在是preStart+leftlen?因为之前是整个前序序列,现在是左子树,整个前序序列是preorder[0 到 preorder.length-1],左子树是preorder[preStart+1,(preStart+1)+(leftlen-1)]变为preorder[preStart+1,preStart+leftlen],leftlen是每次更新的,表示左子树长度,用中序序列算出来的,good

    中序序列启始点:为什么之前是inStart=0,现在还是inStart?因为中序遍历的左子树本来就在左边,从最左边开始没问题,good

    中序序列终点:为什么之前右子树终点是inorder.length-1,现在是i-1?因为根节点是i,所有中序遍历的左子树终点是i-1,good

    返回值:为什么返回值node.left?因为子树的根节点node就是母树的左子树根节点node.left.

    解释右子树:node.right=buildTree(preorder, preStart+leftlen+1,preEnd, map, i+1, inEnd);
    之前是 return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);

    前序序列启始点:为什么之前是preStart=0,现在是preStart+leftlen+1?之前是整个树,现在是右子树,右子树根节点从 preStart+leftlen+1 开始。

    前序序列终点:为什么之前是preorder.length-1,现在是preEnd(即还是preorder.length-1)?对于前序
    序列(中左右)来说,根节点在最前面,整个树的结束和右子树的结束是一样的。

    中序序列启始点:为什么之前是inStart=0,现在还是i+1?因为之前的整个树,所以中序遍历从下标0开始,现在是右子树,刚才算出根节点在中序序列的下标识i,所以右子树中,中序序列从(i+1)开始。

    中序序列终点:为什么之前右子树终点是inorder.length-1,现在是inEnd(即还是inorder.length-1)?对于中序序列(左中右)来说,根节点在中间,整个树的结束和右子树的结束是一样的。

    返回值:为什么返回值node.right?因为对于右子树来说,子树的根节点node就是母树的左子树根节点node.right.

    关于中序序列从数组变为map,为什么新得到的map,key存放数组元素,value存放数组下标?
    这是由map这个数据结构从查找性质决定的,在map中,根据key可以找到唯一确定的value,但是通过value无法找到唯一确定的key,每次通过前序序列确定根节点后,要通过中序序列确定根节点的位置,所有只能下标放value,元素放在key。

    为什么buildTree()方法最后返回来一个node?
    这个node是整个树的根节点,将整个树构建完成后返回这个根节点,为什么呢?因为只有从这个根节点,就可以遍历整颗树(无论是前序遍历、中序遍历还是后序遍历),所以返回了整个树的根节点就相当于返回了整个二叉树。

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

    根据一棵树的中序遍历与后序遍历构造二叉树,力扣106题

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

    例如,给出

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

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7
    

    分析:
    有了上面的分析,那么通过一个后序遍历和中序遍历去构造一棵二叉树,其实原理和前面的也是一样的。

    中序遍历:遍历规则为([左侧区域],根,[右侧区域])。
    后序遍历:遍历规则为([左侧区域],[右侧区域],根)。

    具体实现的代码为:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
       public TreeNode buildTree(int[] inorder,int[] postorder) {
    		if(postorder.length==0)
    			return null;
    		Map<Integer, Integer>map=new HashMap<Integer, Integer>();
    		for(int i=0;i<inorder.length;i++)
    		{
    			map.put(inorder[i], i);  // 中序序列从数组变为map
    		}
    		//六个参数,前三个参数是后序序列,后三个参数是中序序列
    		return buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);
        }
    
    	private TreeNode buildTree(int[] postorder, int postStart, int postEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
    		if(postEnd<postStart||inEnd<inStart)
    			return null;
    		TreeNode node=new TreeNode(postorder[postEnd]);
    		int i=map.get(postorder[postEnd]);
    			
    		int leftlen=i-inStart;
    		
    		node.left=buildTree(postorder, postStart,postStart+leftlen-1, map, inStart, i-1);
    		node.right=buildTree(postorder, postStart+leftlen,postEnd-1, map, i+1, inEnd);           return node;		
    	}
    }
    

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

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7
    

    如果理解了leetcode105,这个就很容易理解了,没必要写了,还是写一下吧

    解释左子树:node.left=buildTree(postorder, postStart,postStart+leftlen-1, map, inStart, i-1);
    之前是 buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);

    后序序列启始点:为什么之前是preStart=0,现在还是0?因为后序序列(左右中),母树的最左节点也就是左子树的最左节点。

    后序序列终点:为什么之前是preorder.length-1,现在是preStart+leftlen-1?之前是母树是后序序列,现在是母树的左子树的后序序列,对于母树的左子树的后序序列,由于长度为leftlen,所以最后一个节点就是 preStart+leftlen-1 。

    中序序列启始点:为什么之前是inStart=0,现在还是inStart?对于中序序列(左中右),母树的最左节点也就是左子树的最左节点。

    中序序列终点:为什么之前右子树终点是inorder.length-1,现在是i-1?对于中序序列(左中右),由于确定了根节点所在下标是i,所有左子树最后节点就是i-1。

    返回值:为什么返回值node.left?因为子树的根节点node就是母树的左子树根节点node.left.

    解释右子树:node.right=buildTree(postorder, postStart+leftlen,postEnd-1, map, i+1, inEnd);
    之前是 buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);

    后序序列启始点:为什么之前是preStart=0,现在是preStart+leftlen?现在是右子树,对于后序序列来说(左右中),右子树的开始节点就是,左子树开始节点postStart + 左子树长度leftlen,所以就是preStart+leftlen。

    后序序列终点:为什么之前是preorder.length-1,现在是preEnd-1(即还是preorder.length-2)?现在是遍历右子树,对于后序序列来说,最后一个是母树的根节点,所有要去掉,所以就是preEnd-1了。

    中序序列启始点:为什么之前是inStart=0,现在还是i+1?对于中序序列(左中右),由于确定了根节点所在下标是i,所以右子树最后节点就是i+1。

    中序序列终点:为什么之前右子树终点是inorder.length-1,现在是inEnd(即还是inorder.length-1)?对于中序序列(左中右),母树最右端也就是右子树最右端,所以是一样的。

    返回值:为什么返回值node.right?因为对于右子树来说,子树的根节点node就是母树的左子树根节点node.right.

    展开全文
  • 概述在上一篇文章中讲到顺序存储二叉树,一般是用于完全二叉树,通过统一的数学公式可以将数组还原成完全二叉树而对于普通的二叉树来说,也可以根据前序、中序和后序遍历得到的数组,还原二叉树还原还原的情况分两种...

    概述在上一篇文章中讲到顺序存储二叉树,一般是用于完全二叉树,通过统一的数学公式可以将数组还原成完全二叉树

    而对于普通的二叉树来说,也可以根据前序、中序和后序遍历得到的数组,还原二叉树

    还原还原的情况分两种,分别是根据前序、中序和根据中序、后序

    采用的二叉树如下图所示:d2c54f9b3904e26c3527374dedb68300.png

    注意:前序和后序是没有办法还原二叉树

    根据前序、中序还原二叉树如下图所示:92afe7fb468b55d589b1427e2b727869.png

    基本思路:根据前序数组,我们能够确定根节点(因为前序数组的根节点一定是第一个)

    中序数组根据根节点能够确定左右子树的位置。(因为中序数组的根节点一定能够分开左右子树)

    前序数组根据中序数组的左右子树的位置,也能够确定自己根节点的左右子树的位置(这部分可以看看代码怎么写的)

    然后再分别递归左子树的前序、中序以及右子树的前序、中序,直到最后左右子树的长度都为0

    代码如下:/**

    * * @param pre 前序数组

    * @param middle 中序数组

    * @return 返回根节点

    */

    public static TreeNode buildTree(int[] pre, int[] middle){

    if (pre == null || middle == null || pre.length == 0 || middle.length == 0 || pre.length != middle.length)

    return null;

    //首先找到根节点

    TreeNode root = new TreeNode(pre[0]);

    //根据根节点的值找到中序遍历中的根节点的位置索引

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到前序和中序中的左子树

    //copyOfRange:拷贝[from, to)区间里的数据,左闭右开

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftPre = Arrays.copyOfRange(pre, 1, rootIndex + 1);

    //找到前序和中序中的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middle.length);

    int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);

    //用递归再次构建左右子树

    TreeNode left = buildTree(leftPre, leftMiddle);

    TreeNode right = buildTree(rightPre, rightMiddle);

    //将左右子树添加到根节点上

    root.left = left;

    root.right = right;

    return root;

    }

    根据中序、后序还原二叉树根据中序、后序和根据前序、中序是一样的道理,只不过是根节点从前序的第一个变为后序的最后一个,如下图所示:eb4c0c70ee21f1b777eddcdcae4f875e.png

    代码如下://根据中序和后序还原二叉树

    /**

    * * @param middle 中序数组

    * @param last 后序数组

    * @return 根节点

    */

    public static TreeNode buildTree2(int[] middle, int[] last){

    if (middle == null || last == null) return null;

    int middleLen = middle.length; //获取中序数组的长度

    int lastLen = last.length; //获取后序数组的长度

    if (middleLen == 0 || lastLen == 0) return null;

    //首先根据后序获取根节点

    TreeNode root = new TreeNode(last[lastLen - 1]);

    //根据root获取中序的根节点的索引值

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到中序和后序的左子树

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftLast = Arrays.copyOfRange(last, 0, rootIndex);

    //找到中序和后序的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middleLen);

    int[] rightLast = Arrays.copyOfRange(last, rootIndex, lastLen - 1);

    //用递归再次构建左子树和右子树

    TreeNode left = buildTree2(leftMiddle, leftLast);

    TreeNode right = buildTree2(rightMiddle, rightLast);

    //将左右子树添加到根节点

    root.left = left;

    root.right = right;

    return root;

    }

    总体代码//树节点:

    public class TreeNode {

    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int val){

    this.val = val;

    }

    }

    //还原代码:

    public class Travel {

    public static void preorder_Traversal(TreeNode node){

    if (node == null)

    return;

    System.out.println(node.val);

    preorder_Traversal(node.left);

    preorder_Traversal(node.right);

    }

    public static void inorder_Traversal(TreeNode node, int val){

    if (node == null)

    return;

    inorder_Traversal(node.left, val);

    System.out.println("---" + node.val);

    if (node.val == val){

    System.out.println("找到了:" + node.val);

    return ; }

    inorder_Traversal(node.right, val);

    }

    public static void postorder_Traversal(TreeNode node){

    if (node == null)

    return;

    postorder_Traversal(node.left);

    postorder_Traversal(node.right);

    System.out.println(node.val);

    }

    public static int getIndex(int[] arr, int target){

    for (int i = 0; i < arr.length; i ++){

    if (arr[i] == target){

    return i;

    }

    }

    return -1;

    }

    //根据前序和中序还原二叉树

    /**

    * * @param pre 前序数组

    * @param middle 中序数组

    * @return 返回根节点

    */

    public static TreeNode buildTree(int[] pre, int[] middle){

    if (pre == null || middle == null || pre.length == 0 || middle.length == 0 || pre.length != middle.length)

    return null;

    //首先找到根节点

    TreeNode root = new TreeNode(pre[0]);

    //根据根节点的值找到中序遍历中的根节点的位置索引

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到前序和中序中的左子树

    //copyOfRange:拷贝[from, to)区间里的数据,左闭右开

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftPre = Arrays.copyOfRange(pre, 1, rootIndex + 1);

    //找到前序和中序中的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middle.length);

    int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);

    //用递归再次构建左右子树

    TreeNode left = buildTree(leftPre, leftMiddle);

    TreeNode right = buildTree(rightPre, rightMiddle);

    //将左右子树添加到根节点上

    root.left = left;

    root.right = right;

    return root;

    }

    //根据中序和后序还原二叉树

    /**

    * * @param middle 中序数组

    * @param last 后序数组

    * @return 根节点

    */

    public static TreeNode buildTree2(int[] middle, int[] last){

    if (middle == null || last == null) return null;

    int middleLen = middle.length; //获取中序数组的长度

    int lastLen = last.length; //获取后序数组的长度

    if (middleLen == 0 || lastLen == 0) return null;

    //首先根据后序获取根节点

    TreeNode root = new TreeNode(last[lastLen - 1]);

    //根据root获取中序的根节点的索引值

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到中序和后序的左子树

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftLast = Arrays.copyOfRange(last, 0, rootIndex);

    //找到中序和后序的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middleLen);

    int[] rightLast = Arrays.copyOfRange(last, rootIndex, lastLen - 1);

    //用递归再次构建左子树和右子树

    TreeNode left = buildTree2(leftMiddle, leftLast);

    TreeNode right = buildTree2(rightMiddle, rightLast);

    //将左右子树添加到根节点

    root.left = left;

    root.right = right;

    return root;

    }

    public static void main(String[] args) {

    //前序、中序测试

    // int[] pre = {18, 20, 16, 29, 39, 8};

    // int[] middle = {16, 20, 39, 8, 29, 18};

    //

    // TreeNode root = buildTree(pre, middle);

    // preorder_Traversal(root);

    //中序、后序测试

    int[] middle = {16, 20, 18, 39, 29, 8};

    int[] last = {16, 20, 39, 8, 29, 18};

    TreeNode node = buildTree2(middle, last);

    preorder_Traversal(node);

    }

    }

    展开全文
  • 概述在上一篇文章中讲到顺序存储二叉树,一般是用于完全二叉树,通过统一的数学公式可以将数组还原成完全二叉树而对于普通的二叉树来说,也可以根据前序、中序和后序遍历得到的数组,还原二叉树还原还原的情况分两种...

    概述在上一篇文章中讲到顺序存储二叉树,一般是用于完全二叉树,通过统一的数学公式可以将数组还原成完全二叉树

    而对于普通的二叉树来说,也可以根据前序、中序和后序遍历得到的数组,还原二叉树

    还原还原的情况分两种,分别是根据前序、中序和根据中序、后序

    采用的二叉树如下图所示:

    注意:前序和后序是没有办法还原二叉树

    根据前序、中序还原二叉树如下图所示:

    基本思路:根据前序数组,我们能够确定根节点(因为前序数组的根节点一定是第一个)

    中序数组根据根节点能够确定左右子树的位置。(因为中序数组的根节点一定能够分开左右子树)

    前序数组根据中序数组的左右子树的位置,也能够确定自己根节点的左右子树的位置(这部分可以看看代码怎么写的)

    然后再分别递归左子树的前序、中序以及右子树的前序、中序,直到最后左右子树的长度都为0

    代码如下:/**

    * * @param pre 前序数组

    * @param middle 中序数组

    * @return 返回根节点

    */

    public static TreeNode buildTree(int[] pre, int[] middle){

    if (pre == null || middle == null || pre.length == 0 || middle.length == 0 || pre.length != middle.length)

    return null;

    //首先找到根节点

    TreeNode root = new TreeNode(pre[0]);

    //根据根节点的值找到中序遍历中的根节点的位置索引

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到前序和中序中的左子树

    //copyOfRange:拷贝[from, to)区间里的数据,左闭右开

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftPre = Arrays.copyOfRange(pre, 1, rootIndex + 1);

    //找到前序和中序中的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middle.length);

    int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);

    //用递归再次构建左右子树

    TreeNode left = buildTree(leftPre, leftMiddle);

    TreeNode right = buildTree(rightPre, rightMiddle);

    //将左右子树添加到根节点上

    root.left = left;

    root.right = right;

    return root;

    }

    根据中序、后序还原二叉树根据中序、后序和根据前序、中序是一样的道理,只不过是根节点从前序的第一个变为后序的最后一个,如下图所示:

    代码如下://根据中序和后序还原二叉树

    /**

    * * @param middle 中序数组

    * @param last 后序数组

    * @return 根节点

    */

    public static TreeNode buildTree2(int[] middle, int[] last){

    if (middle == null || last == null) return null;

    int middleLen = middle.length; //获取中序数组的长度

    int lastLen = last.length; //获取后序数组的长度

    if (middleLen == 0 || lastLen == 0) return null;

    //首先根据后序获取根节点

    TreeNode root = new TreeNode(last[lastLen - 1]);

    //根据root获取中序的根节点的索引值

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到中序和后序的左子树

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftLast = Arrays.copyOfRange(last, 0, rootIndex);

    //找到中序和后序的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middleLen);

    int[] rightLast = Arrays.copyOfRange(last, rootIndex, lastLen - 1);

    //用递归再次构建左子树和右子树

    TreeNode left = buildTree2(leftMiddle, leftLast);

    TreeNode right = buildTree2(rightMiddle, rightLast);

    //将左右子树添加到根节点

    root.left = left;

    root.right = right;

    return root;

    }

    总体代码//树节点:

    public class TreeNode {

    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int val){

    this.val = val;

    }

    }

    //还原代码:

    public class Travel {

    public static void preorder_Traversal(TreeNode node){

    if (node == null)

    return;

    System.out.println(node.val);

    preorder_Traversal(node.left);

    preorder_Traversal(node.right);

    }

    public static void inorder_Traversal(TreeNode node, int val){

    if (node == null)

    return;

    inorder_Traversal(node.left, val);

    System.out.println("---" + node.val);

    if (node.val == val){

    System.out.println("找到了:" + node.val);

    return ; }

    inorder_Traversal(node.right, val);

    }

    public static void postorder_Traversal(TreeNode node){

    if (node == null)

    return;

    postorder_Traversal(node.left);

    postorder_Traversal(node.right);

    System.out.println(node.val);

    }

    public static int getIndex(int[] arr, int target){

    for (int i = 0; i < arr.length; i ++){

    if (arr[i] == target){

    return i;

    }

    }

    return -1;

    }

    //根据前序和中序还原二叉树

    /**

    * * @param pre 前序数组

    * @param middle 中序数组

    * @return 返回根节点

    */

    public static TreeNode buildTree(int[] pre, int[] middle){

    if (pre == null || middle == null || pre.length == 0 || middle.length == 0 || pre.length != middle.length)

    return null;

    //首先找到根节点

    TreeNode root = new TreeNode(pre[0]);

    //根据根节点的值找到中序遍历中的根节点的位置索引

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到前序和中序中的左子树

    //copyOfRange:拷贝[from, to)区间里的数据,左闭右开

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftPre = Arrays.copyOfRange(pre, 1, rootIndex + 1);

    //找到前序和中序中的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middle.length);

    int[] rightPre = Arrays.copyOfRange(pre, rootIndex + 1, pre.length);

    //用递归再次构建左右子树

    TreeNode left = buildTree(leftPre, leftMiddle);

    TreeNode right = buildTree(rightPre, rightMiddle);

    //将左右子树添加到根节点上

    root.left = left;

    root.right = right;

    return root;

    }

    //根据中序和后序还原二叉树

    /**

    * * @param middle 中序数组

    * @param last 后序数组

    * @return 根节点

    */

    public static TreeNode buildTree2(int[] middle, int[] last){

    if (middle == null || last == null) return null;

    int middleLen = middle.length; //获取中序数组的长度

    int lastLen = last.length; //获取后序数组的长度

    if (middleLen == 0 || lastLen == 0) return null;

    //首先根据后序获取根节点

    TreeNode root = new TreeNode(last[lastLen - 1]);

    //根据root获取中序的根节点的索引值

    int rootIndex = getIndex(middle, root.val);

    if (rootIndex == -1)

    return null;

    //找到中序和后序的左子树

    int[] leftMiddle = Arrays.copyOfRange(middle, 0, rootIndex);

    int[] leftLast = Arrays.copyOfRange(last, 0, rootIndex);

    //找到中序和后序的右子树

    int[] rightMiddle = Arrays.copyOfRange(middle, rootIndex + 1, middleLen);

    int[] rightLast = Arrays.copyOfRange(last, rootIndex, lastLen - 1);

    //用递归再次构建左子树和右子树

    TreeNode left = buildTree2(leftMiddle, leftLast);

    TreeNode right = buildTree2(rightMiddle, rightLast);

    //将左右子树添加到根节点

    root.left = left;

    root.right = right;

    return root;

    }

    public static void main(String[] args) {

    //前序、中序测试

    // int[] pre = {18, 20, 16, 29, 39, 8};

    // int[] middle = {16, 20, 39, 8, 29, 18};

    //

    // TreeNode root = buildTree(pre, middle);

    // preorder_Traversal(root);

    //中序、后序测试

    int[] middle = {16, 20, 18, 39, 29, 8};

    int[] last = {16, 20, 39, 8, 29, 18};

    TreeNode node = buildTree2(middle, last);

    preorder_Traversal(node);

    }

    }

    展开全文
  • 思路:中序遍历顺序为左子树-根-右子树, 后序遍历顺序为 左子树-右子树-根,故通过后序遍历可以确定树的根节点,再通过根节点在中序遍历中确定左子树右子树,递归实现以上过程完成树的构造。 图源:...
  • 与之前的 已知前序遍历序列和中序遍历序列 类似,只不过这里的根节点是由后序遍历序列的最后一个节点确定根节点 inLeft表示中序遍历序列的起始下标,inRight表示中序遍历序列的终止下标,用post_Left表
  • 二叉树的前序、中序后序遍历的定义:前序遍历...给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。变量条件:二叉树中的结点名称以大写字母表示:A,B,C.....
  • 根据先序遍历和中序遍历,确定二叉树后,可以给出后序遍历或层序遍历。 public int findIndexInArray(int[] array , int data , int begin , int end){ for(int i = begin ; i <= end ; i++){ if(data ==
  • 而只知道前序和后序遍历的结果是没办法确定唯一一个二叉树的,因为可能有多种情况。所以这里为了简化问题,暂时提出一个限制条件:如果根节点只有一个子节点那么这个节点规定为左节点。 直接上代码: public class ...
  • 在学习树中有这样一个问题,如何根据一颗二叉树的先序序列及中序序列确定二叉树,或是根据后序序列和中序序列确定二叉树。(只有先序和后序是无法唯一确定一颗二叉树的)在网上查资料的时候很少看到将两个合起来写的...
  • //根据先序遍历结果和中序遍历结果确定唯一的二叉树,根据中序遍历结果和后序遍历结果确定唯一的二叉树 import java.util.*; public class Rebuild_Tree { public static void main(String args[]){ int pre[]=new...
  • 但是如果仅知道二叉树的前序和后序序列,一般是不能唯一确定一棵二叉树的,但是可以分析有多少种可能的二叉树,这个没有具体研究,只知道节点少的情况还能凑合分析出来,但是节点多的情况下可能性太多,很难分析。...
  • 1,确定递归函数的参数返回值。 2,确定终止条件。 3,确定单层递归的逻辑。 其实就是模板,改变访问顺序 前序递归 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = ...
  • 例如,给出 中序遍历 inorder = [9,3,15,20,7] ...//用前序遍历和中序遍历确定二叉树类似 import java.util.*; class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { ...
  • 题目描述 二叉树的前序、中序后序遍历的定义: ...给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。 输入 两个字符串,其长度n均小...
  • 一、前序遍历、中序遍历和后序遍历概念 前序遍历: 先输出父节点,再遍历左子树和右子树 中序遍历: 先遍历左子树, 再输出父节点,再遍历右子树 后序遍历: 先遍历左子树,再遍历右子树, 最后输出父节点 小结: 看...
  • 一、二叉树的前序遍历、中序遍历和后序遍历概念 前序遍历: 先输出父节点,再遍历左子树和右子树 中序遍历: 先遍历左子树, 再输出父节点,再遍历右子树 后序遍历: 先遍历左子树,再遍历右子树, 最后输出父节点 小...
  • 对于二叉树,由前序遍历和中序遍历或中序遍历和后序遍历都可以还原二叉树,但是由前序遍历和后序遍历无法还原二叉树,因为无法确定左子树和右子树的位置。根据前序遍历和中序遍历还原二叉树:由前序遍历的第一个值...
  • 找到根在中序遍历的位置,位置左边就是二叉树的左孩子,位置右边是二叉树的右孩子,如果跟结点左边或右边为空,那么该方向子树为空;如果根节点左边右边都为空,那么根节点已经为叶子节点。 (3)对二叉树的左、...
  • 例如,给出: 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] ...//中序遍历和后序遍历可唯一地确定一棵二叉树 import java.util.*; class Solution { public TreeNode buildTree(int[] pre...
  • 菜鸟发现了一个题目,还原二叉树的。 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建...众所周知,前序+中序|中序+后序|中序+层次 是可以唯一确定二叉树的。 根据题目中的例子,菜鸟在纸上把他们写了下来。...
  • * 或者由前后序以及中序遍历中来还原二叉树,前序和后序并不能唯一确定二叉树。 */ public class BinaryTree { // 二叉树的根节点 private Node root; public BinaryTree(int[] array) { createBinT
  • 重建二叉树java

    2020-05-11 15:14:23
    我们知道,可以通过二叉树的前序遍历、中序遍历、后序遍历可以确定唯一的一颗二叉树。事实上我们可以从前序/中序后序/中序得到一颗唯一的二叉树,而前序/后序得到的二叉树不唯一(读者可以自行验证) 注意:以下...
  • 算法思想:已知先序遍历和中序遍历,如何求后序遍历?(1)确定树的根结点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根。(2)求解树的子树。找到根在中序遍历的位置,...
  • 前序和中序确定一棵唯一的二叉树

    千次阅读 2018-10-27 05:39:30
    目标:给定二叉树前序和中序遍历的顺序,构建一棵二叉树,并输出它的前中后序遍历顺序 以下图为例: Node.java public class Node { public int value; public Node left; public Node right; public ...
  • 由于先序遍历树的规则为:根左右,因此可以得到...由先序遍历和中序遍历求解二叉树的过程,步骤如下:①确定树的根节点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根...
  • 题目描述 二叉树的前序、中序后序遍历的定义: 前序遍历:对... 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。 输入描述: 两个字符串,其长度n均小于...
  • 构建二叉树java

    千次阅读 2017-11-12 13:02:17
    第二个就是任何n(n>=0)个不同节点的二叉树,都可由它的中序序列和后序序列唯一确定。(定理的证明可自行查阅资料) 现在我们就利用这两个定理来构建二叉树。 首先我们知道二叉树的先序序列是1234567,中序序列是...
  • 1265: 输出二叉树

    2019-04-11 16:43:23
    我们知道二叉树的先序序列和中序序列或者是中序和后序能够唯一确定一颗二叉树。现在给一颗二叉树的先序序列和中序序列,要求输出它的后序序列。 输入 多组测试数据,每组测试数据格式如下: 第一行为先序序列 第二...
  • 思路一般情况下,需要采用前/后序遍历和中序遍历才能确定一个二叉树,但是其实可以只采用前序遍历(从根结点开始),将空结点(null)输出为一个特殊符号(如“$”),就可以确定一个二叉树了。将二叉树序列化为字符串,...

空空如也

空空如也

1 2 3
收藏数 50
精华内容 20
关键字:

中序和后序确定二叉树java

java 订阅