面试题07. 重建二叉树

重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

提示：
0 <= 节点个数 <= 5000

转载来源：力扣（LeetCode）

题目分析

众所周知：

• 先序遍历的首先遍历的是根节点，所以先序遍历结果的第一个值是根节点的值
• 中序遍历先遍历的是根节点的左子树，接着是根节点的值，再是根节点的右子树，所以中序遍历根节点的值左边的是根节点的左子树中序遍历结果，右边是右子树的中序遍历结果

根据上面的两个基本知识，这道题就基本差不多了:

  1. 根据[3,9,20,15,7]，可以知道这棵树的根节点是3
  2. 根据[9,3,15,20,7]，找到根节点的位置，可以知道左子树为[9]，右子树为[15,20,7]
  3. 序列[9]回到1，构建出节点3的左子树，序列[15,20,7]回到1，构建出节点3的右子树
  4. 返回结果

我的做法是遍历中序数组去寻找根节点的位置，所以时间复杂度是O(N*LogN)，看了题解，发现大牛们使用HashMap<TreeNode,Integer>来存放数组，实现了O(1)的寻找节点，所以他们做法的时间复杂度是O(N)，但是算法的思路适合我上面的一样的，我就不贴他们的代码了。下面是我的代码：

    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0)
            return null;
        this.preorder = preorder;
        this.inorder = inorder;
        return buildTree(0, preorder.length - 1, 0, preorder.length - 1);
    }

    private TreeNode buildTree(int headPreOrder, int tailPreOrder, int headInOrder, int tailInOrder) {
        if (headPreOrder < 0 || tailPreOrder >= preorder.length || headPreOrder > tailPreOrder)
            return null;
        if (headInOrder < 0 || tailInOrder >= preorder.length || headInOrder > tailInOrder)
            return null;
        if (headPreOrder == tailPreOrder)
            return new TreeNode(preorder[headPreOrder]);
//      先序遍历里的第一个就是头结点
        TreeNode root = new TreeNode(preorder[headPreOrder]);

//      找出头结点在中序遍历的位置,从而得到左子树和右子树
        int headInInorderIndex = 0;
        for (int i = headInOrder; i <= tailInOrder; i++) {
            if (preorder[headPreOrder] == inorder[i]) {
                headInInorderIndex = i;
                break;
            }
        }
//      左子树里的节点的个数
        int leftSize = headInInorderIndex - headInOrder;
        root.left = buildTree(headPreOrder + 1, headPreOrder + leftSize, headInOrder, headInInorderIndex - 1);
        root.right = buildTree(headPreOrder + leftSize + 1, tailPreOrder, headInInorderIndex + 1, tailInOrder);
        return root;
    } 

代码文件