欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指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。(真是菜啊)

剑指offer-重建二叉树

如图所示,划分后的中序序列的左半部分是要用来构建根节点的左子树的,这一部分的长度刚好是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的偏移量应该刚好是左子树序列的长度才对,想到了“一段长度”这个概念会更早发现错误。

相关标签: 刷题