重建二叉树

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

分析

1、前中后序遍历的原理一定要搞懂！！！所有的遍历都是以“根”节点为参照的。下面我将左孩子节点称为“左”，右孩子节点称为“右”，根节点称为“中”。

前序遍历就是根节点在前边，中序遍历就是根节点在中间，后序遍历就是根节点在后边！个人感觉这样记的特别准。

前序遍历：中，左，右 中序遍历：左，中，右 后序遍历：左，右，中 2、定义 前序遍历pre = {1,2,4,7,3,5,6,8}，中序遍历in = {4,7,2,1,5,3,8,6}

首先可以根据前序遍历确定根节点为1；

找到根节点在中序遍历中的位置为in[3]；

将二叉树切割成左右子树，其中in[3]左边为左子树，in[3]右边为右子树；

切割后，左子树前序遍历为{2,4,7}，左子树中序遍历为{4,7,2}；

右子树前序遍历为{3,5,6,8}，右子树中序遍历为{5,3,8,6}；

对子树再使用上述方法，即递归调用！

java代码实现

二叉树类的简单定义

public class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int x){ val = x; } }

重建二叉树代码实现

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]){ root.letf = 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; /* 在使用Arrays.copyOfRange(T[ ] original,int from,int to)方法时， 首先要导入 java.util.Arrays包； 该方法的作用是：将original数组从下标from开始直到上标to进行复制，生成一个新的数组， 新数组中包括下标from的元素，不包括上标to的元素； */ } } return root; } }