关注
在递归调用中,传递的数组和中序遍历的整个大数组是不同的,你不能用整个大数组的索引来代替递归传递的小数组中索引。
以调用左子树时,确定下次递归调用的前序数组的边界情况下
数组的边界是
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的左右子树的时候,进行下一次递归的时候发生越界。
主要的原因就是,你需要更新每次递归的时,计算对应数组的一个偏移量,而不是直接用整个中序的索引直接计算。
查看原帖
4 2
相关推荐
牛客热帖
- 1... 想来字节技术实习,看我这篇就够了!——保姆级面经大放送1.9W
- 2... 外卖员面试经验1.7W
- 3... 25届第一份实习怎么找?1.4W
- 4... 0实习经验上岸字节,分享一下过程经验1.2W
- 5... 【0429快问快答】99%牛油的疑惑解答(更新至38个问题1.1W
- 6... 【奖】休息放松or学习提升,五一假期和牛牛一起“充充电”🔋1.1W
- 7... 准备去参加自己的婚礼9369
- 8... 美团后端日常实习一二面(已oc)8140
- 9... 【💰有奖征集】非技术岗位笔面经邀你来分享!攒人品时间到!5765
- 10... 阿里国际 笔试 04295329
正在热议
# 牛友的五一计划 #
18443次浏览 380人参与
# 晒一晒我的offer #
2830015次浏览 49968人参与
# 牛客帮帮团来啦!有问必答 #
400546次浏览 7834人参与
# 无实习如何秋招上岸 #
173311次浏览 2727人参与
# 如何看待offer收割机的行为 #
194610次浏览 2989人参与
# 如何一边实习一边秋招 #
201804次浏览 4008人参与
# 华为求职进展汇总 #
442691次浏览 4446人参与
# 春招别灰心,我们一人来一句鼓励 #
21540次浏览 312人参与
# 产品实习,你更倾向大公司or小公司 #
31275次浏览 491人参与
# 非技术岗薪资爆料 #
8953次浏览 187人参与
# 硬件人的春招flag #
14564次浏览 199人参与
# 女生做医疗销售有前景吗 #
3888次浏览 49人参与
# 字节跳动工作体验 #
53923次浏览 1578人参与
# 聊聊这家公司值得去吗 #
63685次浏览 1278人参与
# 第一次面试 #
17870次浏览 276人参与
# 在国企工作的人,躺平了吗? #
73012次浏览 882人参与
# 机械人,你的秋招第一份简历被谁挂了 #
27018次浏览 492人参与
# 来聊聊机械薪资天花板是哪家 #
22917次浏览 180人参与
# 你更愿意参加线上面试还是线下面试? #
6981次浏览 95人参与
# 如何KTV领导 #
7552次浏览 73人参与