【剑指offer】重建二叉树

深碍√TFBOYSˉ_ 2021-11-09 16:24 300阅读 0赞

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

**思路：**  
  
\#前序序列：1 2 3 4 5 6 7  
\#中序序列：3 2 4 1 6 5 7  
\#此算法过程：   
\#pre : 1 2 3 4 5 6 7  
\#tin : 3 2 4 1 6 5 7  
\#-》输入的pre\[0\]是当前node的元素，赋值tree.val = 1比如  
\#-》 检查tin中哪个元素与pre第一个相同（即1）  
\#发现tin中位置3的1为中心节点  
\#-》 先判断是否可分，如果可分，tin分成左右部，3 2 4 和 6 5 7  
\#-》 从左至右检查pre中哪个元素与左边tin中某个元素相同  
\#-》记录tin中相同元素的位置，比如对3 2 4 来说， pre中2为第一个与左边tin中某元素相同的数  
\#-》则左边递归调用输入pre\[k::\],k即2在pre中位置  
\#-》即左边递归输入 pre' 为 2 3 4 5 6 7 ，左边tin为324  
\#-》右边tin同理，递归。。。。输入pre' 为5 6 7 ，右边tin为6 5 7  
  
.......以此无限类推

**代码：**

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.length == 0||in.length == 0){
                return null;
            }
            TreeNode node = new TreeNode(pre[0]);
            for(int i = 0; i < in.length; i++){
                if(pre[0] == in[i]){
                    node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                    node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
                }
            }
            return node;
        }
    }