牛小弟 level
获赞
51
粉丝
2
关注
8
看过 TA
3
重庆大学
2021
Java
IP属地:广东
暂未填写个人简介
私信
关注
2020-05-31 11:52
已编辑
重庆大学 Java
各位牛油们好,需要大家的帮助,有偿~ 我在刷力扣题目时,遇到一道题很费解:从前序与中序遍历序列构造二叉树 原题的题目链接如下: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 一、正确的代码如下: /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  * ...
Ironxin:在递归调用中,传递的数组和中序遍历的整个大数组是不同的,你不能用整个大数组的索引来代替递归传递的小数组中索引。 以调用左子树时,确定下次递归调用的前序数组的边界情况下 数组的边界是 preStart+1,(preStart +1)+ leftNum, 最原始的写法是 preStart+1,(preStart +1)+ rootIndex_Inorder-inStart, 而你的写法是 preStart+1,rootIndex_Inorder+1, 比如示例 [3,9,6,20,15,7] [9,6,3,15,20,7] 3作为根,然后分为[9,6] [20,15,7] 和[9,6] [15,20,7]。以(9,6)为例,当前的prestart=1,rootIndex_Inorder=0,inStart=0,因此用正确做法算出的前序的左子树数组部分是(1+1,1+1+0-0),由于左闭右开,下次递归判断时,由于左右边界相等,知道9没有左子树,因此返回null,而你的算法是(1+1,0+1)越界了。 而你自己的示例是 [3,9,20,15,7] [9,3,15,20,7],会在判断15的左右子树的时候,进行下一次递归的时候发生越界。 主要的原因就是,你需要更新每次递归的时,计算对应数组的一个偏移量,而不是直接用整个中序的索引直接计算。
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客企业服务