题目描述

给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。

方法一： 递归

解题思路

前序遍历的第一个节点就是这颗树的根节点。

在中序遍历中，找到这个根节点，这个根节点的左边元素就是它的左子树上的元素，这个根节点的右边元素就是它的右子树上的元素。

把范围划分好，直到范围上只有一个元素直接生成返回即可。

需要找到根节点在中序遍历上的下标，才能知道它的左子树上有多少个元素，右子树上有多少个元素。为了方便找到下标，可以用 Map 结构来存储 中序遍历数组上 所有元素和其下标 的对应关系。

以下是以 前序遍历为：[8，3，6，7，9] ， 中序遍历为：[3，6，8，9，7] 的演示图：

复杂度分析

时间复杂度：O(N*logN)

需要挨个递归遍历每个元素，总共有 N 个元素;
另外在遍历每个元素的时候，用到了 HashMap 的查找操作，虽然可以认为他的查询操作一般情况下是 O(1) 级别的时间复杂度。但底层可能是链表存储，这样的查询操作的时间复杂度为 O(N)；也可能是红黑树存储，这样的查询操作的时间复杂度为 O(logN)；（采用哪种存储结构和存储的数量有关）
而这里 Map 的结果是有序的，数据量为 N 也不好确定具体是多少，所以最后的时间复杂度为：O(N*logN)。

空间复杂度：O(N)

重建整颗二叉树需要建立每一个节点，总共有 N 个节点，所以空间复杂度为 O(N)

代码示例

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        // 判断特殊情况
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }

        // key ： 中序遍历元素的值；  
        // value ： 中序遍历元素的值 对应的 下标
        // 可以以O(1)的时间复杂度找到元素在中序遍历中对应的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }

        // 返回在 pre[0...pre.length-1] , in[0, in.length-1] 范围上建立二叉树的根节点
        return process(pre, 0, pre.length - 1,
                0, in.length - 1,
                map);

    }


    /**
     * @param pre 前序遍历的数组
     * @param pL  使用到的 前序遍历的数组 的左边界，闭区间
     * @param pR  使用到的 前序遍历的数组 的右边界，闭区间
     * @param inL 使用到的 中序遍历的数组 的左边界，闭区间
     * @param inR 使用到的 中序遍历的数组 的右边界，闭区间
     * @param map 方便找到元素在中序遍历中对应的下标 需要的 数据结构
     * @return 在使用到的 前序遍历数组、中序遍历数组中；生成该范围内的二叉树，返回这个二叉树的 根节点
     */
    public TreeNode process(int[] pre, int pL, int pR,
                            int inL, int inR,
                            HashMap<Integer, Integer> map) {
        // 越界情况，没有二叉树存在，直接返回 null
        if (pL > pR || inL > inR) {
            return null;
        }
        // 只有一个元素，就是根节点，直接返回
        if (pL == pR || inL == inR) {
            return new TreeNode(pre[pL]);
        }
        // 前序遍历的第一个元素就是 根节点
        TreeNode root = new TreeNode(pre[pL]);
        // 找到 根节点在 中序遍历数组里的 下标
        int inIndex = map.get(pre[pL]);
        // 在有效的中序遍历范围里， 根节点左边的元素 都是属于 根节点的左子树
        int leftTreeSize = inIndex - inL;
        // 在左子树的有效范围里，生成左子树
        root.left = process(pre, pL + 1, pL + leftTreeSize,
                inL, inIndex - 1,
                map);
        // 在右子树的有效范围里，生成右子树
        root.right = process(pre, pL + leftTreeSize + 1, pR,
                inIndex + 1, inR,
                map);
        return root;
    } 

}

方法二： 用栈

解题思路

虽然递归方法都可以改写成为非递归的方法实现，但还是要具体问题具体分析。

就该题来说，先了解前序遍历和中序遍历的特点：

前序遍历： 顺序就是所有第一次访问到根节点时的顺序，

如果一个元素有左子树，那么下一个元素的值就是它的左子树的值；

如果没有左子树，就看之前访问的哪个元素有右子树，那么下一个元素的值就是“之前访问有右子树的元素”的那个右子树的值。

中序遍历：顺序就是所有第二次访问到根节点时的顺序。

我们可以结合中序遍历的结果，进而找到具体的哪个元素有右子树，具体思路参照代码流程及注释。

所以，整个流程就是遍历一遍前序遍历的数组，生成相对应的左子树；再结合中序遍历，生成相对应的右子树。

以下是以 前序遍历为：[8，3，6，7，9] ， 中序遍历为：[3，6，8，9，7] 的演示图：

复杂度分析

时间复杂度： O(N)

整个的大流程就是一个 for 循环遍历前序数组，虽然里面有一个 while 循环，但这个 while 循环极端情况下只会发生在前序遍历的某一个元素上，并不是所有元素都会进入 while 循环中，所有时间复杂度为 O(N)。

空间复杂度：O(N)

重建整颗二叉树需要建立每一个节点，总共有 N 个节点，所以空间复杂度为 O(N)

示例代码

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        // 判断特殊情况
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        int preIndex = 0;
        int inIndex = 0;
        // 整颗树的根节点
        TreeNode root = new TreeNode(pre[preIndex]);
        stack.push(root);

        // 遍历 前序遍历的数组， 生成对应的根节点
        for (preIndex = 1; preIndex < pre.length; preIndex++) {
            TreeNode node = stack.peek();
            // 之前压栈的元素 不等于 中序遍历数组中开头的数，
            // 即 之前压栈的元素 有左子树
            if (node.val != in[inIndex]) {
                // 再生成相应的左子树并压栈
                node.left = new TreeNode(pre[preIndex]);
                stack.push(node.left);
            } else {
                // 之前压栈的元素的值 等于 中序遍历数组中开头的数，
                // 即 之前压栈的元素 没有左子树； 继续找那个元素有右子树
                while (!stack.isEmpty() && stack.peek().val == in[inIndex] ) {
                    node = stack.pop();
                    inIndex++;
                }
                // 再生成相应的右子树并压栈
                node.right = new TreeNode(pre[preIndex]);
                stack.push(node.right);
            }
        }

        // 返回整棵树的根节点
        return root;
    } 
}