算法复习：二叉树的镜像

题目描述

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

解题思路

前序遍历中的第一个数字是书的根结点，再重中序遍历中找到根节点，其左边为根的左子树的中序遍历，其右边为根的右子树的中序遍历。由于前序遍历中，紧跟在根节点之后的是左子树，而且长度已知，故可求出左子树和右子树的前序遍历和中序遍历，接着递归即可。 递归的出口：只剩下一个相同数字时即可返回。 代码：

public TreeNode reConstructBinaryTree(int[] pre, int[] in) { if (pre.length == 0) return null; if(pre[0] == in[0] && pre.length == 1)return new TreeNode(pre[0]); int root = pre[0]; TreeNode tnRoot = new TreeNode(root); tnRoot.left = tnRoot.right = null; int i = 0; for(;i < in.length;i++){ if(in[i] == root) break; } int[] leftPre = new int[i]; for(int j = 0,k = 1;k < i + 1;j++,k++){ leftPre[j] = pre[k]; } int[] leftIn = new int[i]; for(int j = 0;j < i;j++){ leftIn[j] = in[j]; } int[] rightPre = new int[pre.length - i -1]; for(int j = 0,k = i + 1;k < pre.length;j++,k++){ rightPre[j] = pre[k]; } int[] rightIn = new int[pre.length - i -1]; for(int j = 0,k = i + 1;k < in.length;j++,k++){ rightIn[j] = in[k]; } tnRoot.left = reConstructBinaryTree(leftPre,leftIn); tnRoot.right = reConstructBinaryTree(rightPre,rightIn); return tnRoot; }

代码写得比较随意，不太规范，具体见《剑指offer》