剑指Offer面试题7：重建二叉树

一、题目

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

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

要求：空间复杂度 O(n)，时间复杂度 O(n)

二、需要掌握的知识

2.1 二叉树

面试的时候提到的树，大部分是二叉树。所谓二叉树是树的一种结构，再二叉树中每个节点最多只能有两个子节点。在二叉树中最重要的莫过于遍历。通常有下面三种遍历方式。

2.2 前序遍历、中序遍历、后序遍历

前序遍历：中左右，先访问中间的根节点，再访问左子节点，再访问右子节点。上图前序遍历结果：1、2、4、7、3、5、6、8

中序遍历：左中右。先访问左子节点，再访问中间根节点，再访问右子节点。上图中序遍历结果：4、7、2、1、5、3、8、6

后序遍历：左右中。先访问左子节点，再访问右子节点，最后访问中间根节点。上图后序遍历结果：7、4、2、5、8、6、3、1

三、解决思路

对于二叉树的前序遍历，序列的第一个元素一定是根节点的值，因为序列没有重复元素，因此中序遍历中可以找到这个值，而中序遍历中根节点将二叉树分成左右子树两个部分而子树的根节点也是相应前序遍历中的首位。

具体做法

1、先根据前序遍历中的第一位建立根节点

2、然后遍历中序遍历找到这个值，这样就确定了根节点在数组中的位置

3、再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树

4、直到子树序列长度为0，结束递归

四、Java代码实现

4.1 递归

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return null;
        //构建根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.length; i++){
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i]){ 
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); 
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }
}

4.2 栈

除了递归，我们也可以用类似非递归前序遍历的方式建立二叉树，利用栈辅助进行非递归，然后依次建立节点。

具体做法：

• step 1：首先前序遍历第一个数字依然是根节点，并建立栈辅助遍历。
• step 2：然后我们就开始判断，在前序遍历中相邻的两个数字必定是只有两种情况：要么前序后一个是前一个的左节点；要么前序后一个是前一个的右节点或者其祖先的右节点。
• step 3：我们可以同时顺序遍历pre和vin两个序列，判断是否是左节点，如果是左节点则不断向左深入，用栈记录祖先，如果不是需要弹出栈回到相应的祖先，然后进入右子树，整个过程类似非递归前序遍历。

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return null;
        Stack<TreeNode> s = new Stack<TreeNode>();
        //首先建立前序第一个即根节点
        TreeNode root = new TreeNode(pre[0]); 
        TreeNode cur = root;
        for(int i = 1, j = 0; i < n; i++){
            //要么旁边这个是它的左节点
            if(cur.val != vin[j]){ 
                cur.left = new TreeNode(pre[i]);
                s.push(cur);
                //要么旁边这个是它的右节点，或者祖先的右节点
                cur = cur.left; 
            }else{
                j++;
                //弹出到符合的祖先
                while(!s.isEmpty() && s.peek().val == vin[j]){
                    cur = s.pop();
                    j++;
                }
                //添加右节点
                cur.right = new TreeNode(pre[i]); 
                cur = cur.right;
            }
        }
        return root;
    }
}