剑指offer-重建二叉树
程序员文章站
2022-06-17 18:53:12
...
代码原作者的代码利用了递归思想,写得很好。链接在此https://cloud.tencent.com/developer/article/1401290
由于本人脑子笨,有些细节地方转不过来(其实以前碰到这种情况也是要想好久)。比如本题代码中的参数问题:
public class Solution {
private TreeNode rebuildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
if(preStart > preEnd | inStart > inEnd)
return null;
// 根节点
TreeNode root = new TreeNode(pre[preStart]);
// 寻找根节点在中序序列的位置
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == pre[preStart]) {
// 可以计算出中序序列的左右子树序列为:左:inStart~i -1,右:i+1~inEnd。
// 前序序列的左右子树:左:preStart+1~preStart+i-inStart,右:preStart+i-inStart+1~preEnd
root.left = rebuildTree(pre,preStart+1, preStart+i-inStart,in, inStart, i - 1);
root.right = rebuildTree(pre,preStart+i-inStart+1, preEnd, in, i+1, inEnd);
}
}
return root;
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root;
root = rebuildTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
return root;
}
}
问题就在以下两句
root.left = rebuildTree(pre,preStart+1, preStart+i-inStart,in, inStart, i - 1);
root.right = rebuildTree(pre,preStart+i-inStart+1, preEnd, in, i+1, inEnd);
在preStart+i-inStart中为什么要减去inStart呢?不减不行吗?反正inStart刚好是0啊?后来自己走了几次代码,递归调用函数后发现inStart虽然在左边,但不会一直是0。(真是菜啊)
如图所示,划分后的中序序列的左半部分是要用来构建根节点的左子树的,这一部分的长度刚好是length=i-inStart,所以在前序序列中,左子树的序列截取范围就是从preStart+1到preStart+length,即preStart+i-inStart,然后右子树的前序序列范围就是preStart+i-inStart+1到preEnd了。
其实以前做题也碰到过类似的情况,某个参数传进去的时候加1或者减1就对了,差了个1就不行。大一的时候刚学冒泡排序,有的地方已经不用遍历到结尾了,传参j<n-i,还不知道为啥,关键也在没弄明白i的改变会有什么影响。二叉树这一题,也犯了类似的错误,本应该宏观一点切割序列,一段一段来看,却只切割了一次,使用了类似暴力的方式从preStart往右边数了几个数字,刚好有i个,于是觉得preStart+i没毛病,错就错在第一遍切割inStart是刚好是0,所以没影响。preStart的偏移量应该刚好是左子树序列的长度才对,想到了“一段长度”这个概念会更早发现错误。
上一篇: 带你认识JAVA的构造函数
下一篇: 新手需要入门实时记忆知识点(不定时更新)
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
[算法练习-剑指offer]题18.二叉树的镜像(Java)
-
剑指offer37.序列化和反序列化二叉树(详解)
-
力扣OJ 剑指 Offer 68 - II. 236. 二叉树的最近公共祖先
-
《剑指offer》面试题6 重建二叉树
-
20200329-剑指offer-面试题48. 最长不含重复字符的子字符串(滑动窗口)
-
剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解
-
剑指 Offer 55 - I. 二叉树的深度——DFS+BFS解题
-
leetcode 面试题32 (剑指offer)- II. 从上到下打印二叉树 II(python3)
-
leetcode 113 剑指offer 面试题34. 二叉树中和为某一值的路径(python3)