剑指Offer面试题07：重建二叉树（根据前序遍历和中序遍历还原树）

r囧r小猫 2023-02-14 01:19 39阅读 0赞

题目：

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

> 例如，给出  
> 前序遍历 preorder = \[3,9,20,15,7\]  
> 中序遍历 inorder = \[9,3,15,20,7\]  
> 返回如下的二叉树：  
> 　3  
> / 　 \\  
> 9 　 20  
> / 　 　\\  
> 15 　　7  
> 限制：  
> 0 <= 节点个数 <= 5000

### 一、二叉树的遍历（复习） ###

首先，二叉树的前序，中序，后续遍历在数据结构里学习过。

前序遍历的顺序是：中 左 右；  
中序遍历：左 中 右；  
后续遍历：左 右 中。

并且遍历的过程都是向下递归进行的。  
也就是说，中是根节点，左 和 右 如果是子树，那么对这两棵子树，也进行前序、中序或者后序遍历。

比如给出例子的那棵树：

3
       / \
      9  20
        /  \
       15   7

按照中左右的顺序：
    1 中：得到了 3；
    2 左：左子树进行前序遍历；
        2.1 中：得到了 9；
        2.2 左：空；
        2.3 右：空；
    3 右：右子树进行前序遍历：
        3.1 中：得到了 20；
        3.2 左：对左子树进行遍历：
            3.2.1 中：得到了 15；
            3.2.2 左：空；
            3.2.3 右：空；
        3.3 右：对右子树进行遍历：
            3.3.1 中：得到了 7；
            3.3.2 左：空；
            3.3.3 右：空。
    结束

得到 前序遍历结果：3 9 20 15 7

同样的，可以得到中序遍历和后序遍历的结果：  
中序遍历：9 3 15 20 7  
后序遍历：9 15 7 20 3

假如给出这样一个二叉树的数据结构：

/**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */

那么对应的前序，中序，后序遍历应该是：

//主方法
        public int[] order(TreeNode root){
        
            //preOrder(root);
            //inOrder(root);
            //postOrder(root);
            int[] ans=new int[ans.size()];
            for(int i=0;i<ans.size();i++){
        
                ans[i]=list.get(i);
            }
            return ans;
        }
    
        //前序方法
        public void preOrder(TreeNode root){
        
            if(root==null){
        
                return;//空，截止。
            }
            list.add(root.val);//中
            preOrder(root.left);//左：递归
            preOrder(root.right);//右：递归
        }
    
        //中序方法
        public void inOrder(TreeNode root){
        
            if(root==null){
        
                return;
            }
            inOrder(root.left);//左：递归
            list.add(root.val);//中
            inOrder(root.right);//右：递归
        }
    
        //后序方法
        public void postOrder(TreeNode root){
        
            if(root==null){
        
                return;
            }
            postOrder(root.left);//左：递归
            postOrder(root.right);//右：递归
            list.add(root.val);//中
        }

### 二、重建二叉树 ###

现在回到这道题本身。

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

知道两个遍历结果，我们还知道前序：中左右，中序：左中右。

根据这两个遍历结果，人工来进行重建：

##### 1. #####

preorder：第一个元素 3 ，**它一定是树的根节点**；  
转到 inorder：3这个节点 ，左边一定是左子树，右边是右子树。

3
     　　  /  \
    　　 [9] [15 20 17]

即 ==9 | 3 | 15 20 17 ==

##### 2. #####

根据刚才的划分，我们可以知道，左子树长度为 1，右子树长度为 3 。

再回到preorder：除了 3 这个根节点外，左右子树可以划分出来：

3
    　　   / \
    　　[9] [20 15 17]

即 3 | 9 | 20 15 17.

##### 3. #####

这样除了根节点3之外，  
**前序序列**，对应的**中序序列**  
都分成了，左右子树。  
那么问题就变成了 　两棵子树 　的　“根据前序和中序遍历推导二叉树”　的子问题。

所以我们可以递归的进行上面1 2两步…………

> 这里面注意 来回跳转：  
> 前序遍历找到一个根节点 **–>** 在中序遍历里用他分开左右子树的位置；  
> 回到前序遍历找到左右子树的根节点 **–>** 再去中序遍历里划分左右子树……

> 再注意，从前序找到根节点之后，要根据它的值，在中序遍历里找到对应位置。  
> 按理说是要循环遍历中序数组，找到位置，但是这里说了值不会重复，所以可以直接用map根据key找到value）

/**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
        
        HashMap<Integer, Integer> dic = new HashMap<>();
        int[] sit;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            sit = preorder;
            //先把中序遍历里的每一个节点和位置对应的关系放入一个字典map里
            //这样在划分的时候就可以直接找到对应的位置，而不用根据值去遍历一次中序数组
            for(int i = 0; i < inorder.length; i++){
        
                dic.put(inorder[i], i);
            }
    
            //调用主方法，传入参数为，根节点root位置为0（前序），整个左右子树范围（中序）
            return recur(0, 0, inorder.length - 1);
        }
    
    
        /**
         * 递归创建树的方法，其实每次只要添加一个根节点的值，然后左右分别递归
         * 参数：子树根节点位置(前序)，子树最左、最右范围（中序
         */
        TreeNode recur(int preRoot, int inLeft, int inRight) {
        
            if(inLeft > inRight){
        
                return null;
            }
            //创建当前的根节点
            TreeNode root = new TreeNode( sit[preRoot] );
    
            //取出这个根节点在中序遍历中的位置
            int i = dic.get( sit[preRoot] );
    
            //根据这个位置i，把中序遍历分成左右两棵子树的中序遍历，再递归
    
            //左子树的根节点: 此次根节点的后一个（前序）
            //子树范围：左不变，右此次根节点的左一个位置（中序）
            root.left = recur(preRoot + 1, inLeft, i - 1);
    
            //右子树的根节点，此次根节点+左子树长度+1 （前序）。
            //左右划分，左边此次根节点的右一个位置，右边不变（中序）
            root.right = recur(preRoot + i - inLeft + 1, i + 1, inRight);
    
            return root;
        }
    }

另一种方法：可以直接把两个遍历结果都用ArrayList保存起来，这样在每一轮划分的时候，就可以调用ArrayList的sublist方法，直接进行操作。  
（数据不重复，所以用ArrayList也可以直接根据值找到索引位置）

/**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
    
            // 把前序和中序遍历的数组都转换成list
            List<Integer> pre = new ArrayList();
            for(int i : preorder){
        
                pre.add(i);
            }
            List<Integer> in = new ArrayList();
            for(int i : inorder){
        
                in.add(i);
            }
    
            //调用递归的方法，参数是前序遍历和中序遍历的两个listt
            return recur( pre , in );
        }
    
    
        /**
         * 参数：前序和中序的list
         */
        TreeNode recur(List pre, List in){
        
            // 递归停止条件，就是遍历完了列表
            if(pre.size() == 0){
        
                return null;
            }
    
            // 前序遍历的第一个，一定是root
            int val = (int) pre.get(0);
            //把root节点创建出来
            TreeNode root = new TreeNode(val);
    
            // 从找到root在中序遍历里的位置
            int index = in.indexOf(root.val);
    
            //根据位置，对于前序和中序都进行左右划分，然后递归调用自身
            root.left = recur(pre.subList(1,1+index), in.subList(0,index));
            root.right = recur(pre.subList(1+index, pre.size()), in.subList(1+index, in.size()) );
            return root;
        }
    }