qq_31469413 2015-12-30 10:37 采纳率: 0%
浏览 1371

求助,已知二叉树前序终序号求后序的下面这段程序的递归部分的意义,看不懂啊

public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {

    if(startPre>endPre||startIn>endIn)
        return null;
    TreeNode root=new TreeNode(pre[startPre]);

    for(int i=startIn;i<=endIn;i++)
        if(in[i]==pre[startPre]){
                    //就是下面这两句的参数是怎么得来的
            root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
            root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
        }

    return root;
}

}

  • 写回答

1条回答 默认 最新

  • threenewbee 2015-12-30 20:52
    关注

    对于前序,子节点肯定在父节点后面,对于中序,左子节点肯定在父节点前面,右子节点肯定在父节点后面
    据此可以递归构造一个二叉树。方法是,遍历前序序列,构造出父节点,然后根据后序,得到左右,然后递归。
    1,2,4,7,3,5,6,8,从左往右,先是1,因此472是它的左子(包括左子的下一级)(pre,startPre+1,startPre+i-startIn确定),5386是右子(in,startIn,i-1确定)。以此类推

    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥30 用arduino开发esp32控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题