这个题目主要还是理解树的概念。给定一个先序遍历的数组和中序遍历的数组,观察重建二叉树时两个数组之间存在的联系。
先序遍历的结果是 1,2,4,5,3,6,7
中序遍历的结果是 4,2,5,1,6,3,7
可以看到根节点是 1,左子树是2,4,5,右子树是3,6,7
对于左子树来说,
他的先序遍历是 2,4,5
他的中序遍历是 4,2,5
可以看到根节点是 2,左子树是4, 右子树是5
因此一个解题思路是,先在先序数组中找到树或者子树的根节点,然后确定他在中序遍历数组中的下标位置。
那么中序数组中根节点左边的是左子树的长度,右边的是右子树的长度。【左子树】【根节点】【右子树】
因为在先序遍历中,它的结构是这样的 【根节点】【左子树】【右子树】,
所以,可以根据中序遍历中左子树和右子树的长度确定先序中那一部分是左子树,那一部分是右子树。
然后递归建树。
具体代码如下:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.Arrays; public class Solution { /* * 首先理解二叉树的定义,以及二叉树前序遍历和中序遍历的区别。 * 先看一个例子,某二叉树的前序和中序分别是 * 前序 1,2,3,4,5,6,7 * 中序 3,2,4,1,6,5,7 * 然后不断的找到树和子树的根节点,递归的创建树。 * 因此每一次首先要找到树或者子树的根节点,然后在前序中识别左右子树的范围。 * 递归的结束条件是, */ public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if (pre.length == 0 || in.length == 0) return null; int rootvalue = pre[0]; TreeNode root = new TreeNode(rootvalue); // 然后找到中序中的root,再划分左右子树,递归传入 int rootIndexIn = 0; while(in[rootIndexIn]!=rootvalue) rootIndexIn++; root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndexIn+1), Arrays.copyOfRange(in, 0, rootIndexIn)); root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndexIn+1, pre.length), Arrays.copyOfRange(in, rootIndexIn+1, pre.length)); return root; } }