【剑指Offer题解：java】重建二叉树

快来打我* 2022-10-27 13:39 43阅读 0赞

### 文章目录 ###

*   *  题目
     *  分析
     *  代码

## 题目 ##

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

## 分析 ##

根据中序遍历和前序遍历可以确定二叉树，具体过程为：

1.  根据前序序列第一个结点确定根结点
2.  根据根结点在中序序列中的位置分割出左右两个子序列
3.  对左子树和右子树分别递归使用同样的方法继续分解

例如：

前序序列\{1,2,4,7,3,5,6,8\} = pre

中序序列\{4,7,2,1,5,3,8,6\} = in

1.  根据当前前序序列的第一个结点确定根结点，为 1
2.  找到 1 在中序遍历序列中的位置，为 in\[3\]
3.  切割左右子树，则 in\[3\] 前面的为左子树， in\[3\] 后面的为右子树
4.  则切割后的**左子树前序序列**为：\{2,4,7\}，切割后的**左子树中序序列**为：\{4,7,2\}；切割后的**右子树前序序列**为：\{3,5,6,8\}，切割后的**右子树中序序列**为：\{5,3,8,6\}
5.  对子树分别使用同样的方法分解

![image.png][]

![image.png][image.png 1]

![image.png][image.png 2]

## 代码 ##

import java.util.Arrays;
    
    public class Solution { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
             if (pre.length == 0 || in.length == 0) return null;
            //谦虚遍历第一个节点即为根节点
            TreeNode root = new TreeNode(pre[0]);
            //在中序遍历中找到根节点，根节点左边为左子树，右边为右子树
            for (int i = 0; i < in.length; i++) { 
                if (in[i] == pre[0]) { 
                    // 左子树，注意 copyOfRange 函数，左闭右开
                    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                    break;
                }
            }
            return root;
        }
    }

[image.png]: /images/20221024/fe69d01b809d4b99ab96f0160dd7297f.png
[image.png 1]: /images/20221024/bba29baa9d304034bbc3a584029ee81d.png
[image.png 2]: /images/20221024/2745be175b344ba09d6fc0b6266d0863.png