输入某二叉树的前序遍历和中序遍历的结果重建出该二叉树
来源:5-3 二分搜索树的节点插入
我有明珠一颗
2019-08-31
老师,您好,我仔细研读了以下实现代码,有些地方始终想不明白,麻烦解答下,在“??????”处。
/*先来分析一下前序遍历和中序遍历得到的结果, * 前序遍历第一位是根节点; * 中序遍历中,根节点左边的是根节点的左子树,右边是根节点的右子树。 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。 * 首先,根节点 是{ 1 }; * 左子树是:前序{ 2,4,7 } ,中序{ 4,7,2 }; * 右子树是:前序{ 3,5,6,8 } ,中序{ 5,3,8,6 };* * 这时,如果我们把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。 * 这样,一直用这个方式,就可以实现重建二叉树。 * 原文链接:https://blog.csdn.net/leiflyy/article/details/51100687 */ public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {//pre表示什么?????? in:输入数组 if(pre == null || in == null){ return null; } TreeNode mm = reConstructBinaryTreeCore(pre, in, 0, pre.length-1, 0, in.length-1); return mm; } //核心递归 public static TreeNode reConstructBinaryTreeCore(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) { TreeNode tree = new TreeNode(pre[preStart]); tree.left = null; tree.right = null; if (preStart == preEnd && inStart == inEnd) { return tree; } int root = 0; for(root= inStart; root < inEnd; root++){ //?????? 题干中提到不会有重复的数字,这里为什么还要判断如果元素相等呢 if (pre[preStart] == in[root]) { break; } } int leifLength = root - inStart; int rightLength = inEnd - root; if (leifLength > 0) { //??????后面的4个参数为什么要这样写呢 tree.left = reConstructBinaryTreeCore(pre, in, preStart+1, preStart+leifLength, inStart, root-1);//inEnd=root-1,为什么要减掉1 } if (rightLength > 0) { //??????后面的4个参数为什么要这样写呢 tree.right = reConstructBinaryTreeCore(pre, in, preStart+1+leifLength, preEnd, root+1, inEnd); } return tree; }
写回答
1回答
-
1
?????? 题干中提到不会有重复的数字,这里为什么还要判断如果元素相等呢
pre中没有重复的数字,in中没有重复的数字,但是pre中的所有数字,肯定在in中有一份。
2
我觉得注释已经写的很清楚了。
如果前序是 {1,2,4,7,3,5,6,8},中序是 {4,7,2,1,5,3,8,6}
首先根据前序的根1,找到在中序的位置。
然后根据中序中1的位置,就能知道,这棵树左边包含{4, 7, 2},右边包含{5, 3, 8, 6}
我们也知道了,左子树有3个节点,右子树有4个节点;
所以,在前序中,1后面,找到三个节点{2, 4, 7},和四个节点{3, 5, 6, 8}
我们就有了两颗新的子树的现需遍历和中序遍历。
对于左子树:前序:{2, 4, 7},中序:{4, 7, 2}
对于右子树:前序:{3, 5, 6, 8},中序:{5, 3, 8, 6}
然后对两棵子树继续递归。
继续加油。
112019-09-01
相似问题