本文主要是介绍重建二叉树（面试算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
二叉树遍历方式：
前序遍历：按 根节点 ——>左子树（或左节点）——>右子树（或右节点）的顺序进行访问
中序遍历：按 左子树（或左节点）——>根节点 ——>右子树（或右节点）的顺序进行访问
后续遍历：按 左子树（或左节点）——>右子树（或右节点）——>根节点 的顺序进行访问
解题思路：
通过前序遍历所得到的序列中按顺序遍历到的数据要么与后面的数据不是同一子树上的数据，如果在同一子树则该数据必然是该子树的根节点。因此可以顺序遍历前序遍历的序列，再根据遍历到的数据对中序遍历中的数据进行划分，其中在该数据左边的数据为以该数据为根节点的二叉树的左子树上的数据，在其右边的数据为右子树上的数据。这样就可以通过一个递归的方式来对数据进行还原，今天实现代码如下：
代码实现：
public class Solution {static int index = 0;public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if (pre == null || pre.length == 0) {return null;}return reConstructBinaryTree(pre, in, 0, in.length - 1);} public TreeNode reConstructBinaryTree(int [] pre,int [] in, int s, int e) {if (s > e) {return null;}if (index >= pre.length) {return null;}for(int i = s; i <= e; ++i){if (in[i] == pre[index]) {TreeNode result = new TreeNode(pre[index]);++index;result.left = reConstructBinaryTree(pre, in, s, i-1);result.right = reConstructBinaryTree(pre, in, i + 1, e);return result;}}return null;}public static void main(String[] args) {// TODO Auto-generated method stubint[] pre = new int[]{1,2,4,3,5,6};int[] in = new int[]{4,2,1,5,3,6};Solution solution = new Solution();TreeNode result = solution.reConstructBinaryTree(pre, in);System.out.println(result);}}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}
这篇关于重建二叉树（面试算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
