输入某二叉树的前序遍历和中序遍历的结果重建出该二叉树

来源: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回答

liuyubobobo

2019-08-31

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}

然后对两棵子树继续递归。


继续加油。

1
1
我有明珠一颗
醍醐灌顶,非常非常感谢
2019-09-01
共1条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程