重建二叉树 剑指OFFER

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

这题我打算使用递归的方式来编写，函数返回根节点，用游标作为区间构建二叉树。具体思路如下：

• 建立一个节点，将前序遍历的第一个数作为根节点的值
• 找出值在中序遍历序列中的位置
• 将序列拆分，针对左右节点分别进行求根（如果位置与边界重合说明无左（右）子树，将节点赋值为null
• 将子树拉出来单独算入函数（用游标隔出数组，形成子串）
• 返回构造好的节点

  public TreeNode returnRoot(int firstBeg, int firstEnd, int midBeg, int midEnd, int[] arrayList1, int[] arrayList2)
    //beg 第一个数的位置，end 最后一个数的位置 arrayList1 前序数列 arrayList2 中序序列
    {
        if (firstBeg>firstEnd||midBeg>midEnd)
            return null;
        int root_val = arrayList1[firstBeg];
        TreeNode treeNode = new TreeNode(root_val);
        treeNode.val = root_val;
        for (int i = midBeg;i<=midEnd;i++)
        {
            if (arrayList2[i] == root_val)
            {
                treeNode.left = returnRoot(firstBeg+1, firstBeg+i-midBeg, midBeg,i-1, arrayList1, arrayList2);
                treeNode.right = returnRoot(firstBeg+i-midBeg+1, firstEnd, i+1, midEnd, arrayList1, arrayList2);
            }
        }
        return  treeNode;
    }

心得笔记：

通过这道题主要加深了我对java中传参的理解，当传入基本类型时，使用的赋值操作，而传入类对象时是传了引用。

• ArrayList的使用

  arrayList.get(0);//获取第1个元素
  arrayList.indexOf(2);//查询第一个值为2的下标
  

• Scanner的使用

  Scanner scanner = new Scanner(System.in);
  int i = scanner.nextInt;//接受下一个int型变量
  String str = scanner.nextLine;//接受下一个字符串变量