[每日一道小算法（二十三）] [二叉树]重建二叉树（剑指offer习题）

淡淡的烟草味﹌ 2023-07-04 15:53 79阅读 0赞

前言：  
树的概念，一直了解的模模糊糊的，今天正好遇到了这道题，所以来总结一下这方面的知识。

### 树 ###

树是一种在实际编程中经常遇到的数据结构。它的逻辑结构简单，除根节点之外每个节点只有一个父结点；除叶节点之外都用指针链接。  
二叉树是树的一种特殊数据结构，在二叉树中每个节点做多只能有两个子节点。二叉树有三种遍历：

*  前序遍历：先访问根节点，在访问左子节点，最后访问右子节点
 *  中序遍历：先访问左子节点，在访问根节点，最后访问右子节点。
 *  后续遍历：先访问左子节点，在访问右子节点，最后访问根节点。

二叉搜索树，左子节点都小于等于根节点，右子节点都大于等于根节点。我们可以平均在O（logn）的时间内根据数值在二叉查找树中找到一个节点。

二叉树的另外两个特例：堆和红黑树。堆分为最大堆和最小堆。在最大堆中根节点最大，在最小堆中根节点值最小。  
红黑树性质：

*  所有节点不是红色就是黑色
 *  根节点是黑色的
 *  不存在两个相邻的红色节点
 *  每个节点（包含根节点）都任何后代Null节点的每跳路径都包含相同数量的黑色节点。

### 题目描述 ###

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{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
4.  根据当前前序序列的第一个节点确定根节点，为1
5.  找到1在中序序列中得位置，为in\[3\]
6.  切割左右子树，则在in\[3\]前面的为左子树，in\[3\] 后面的为右子树
7.  则切割后的左子树前序序列为：\{2,4,7\}，切割后的左子树中序序列为：\{4,7,2\}；切割后的右子树前序序列为：\{3,5,6,8\}，切割后的右子树中序序列为：\{5,3,8,6\}
8.  对子树分别使用同样的方法分解

### 代码样例 ###

import java.util.Arrays;
    
    /** * 重建二叉树 * 递归分解求解 */
    public class Solution2 { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
            if(pre == null || in == null || 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])// 找到中序序列中的根节点 在此进行分解
                { 
                    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;
        }
    }