【剑指Offer】重建二叉树 题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
二叉树的前序中序后序遍历
做这道题之前我们需要先搞懂二叉树的前序，中序，后序遍历是怎样的。
二叉树是一颗特殊的树，它的每个节点都不能有多于两个的儿子节点。即一颗二叉树最多有两个儿子。如下图所示
而树有三种遍历方式，分别是前序，中序，后序遍历。而前，中，后分别表示的是根节点的遍历顺序。
先遍历根节点，再左节点，再右节点，叫做前序遍历
先左节点，再根节点，再右节点，叫做中序遍历
先左节点，再右节点，再根节点，叫做后序遍历
以上图所示的二叉树为例，分别描述它的前中后序遍历
前序遍历过程
它的前序遍历为ABCDEFGH
前序遍历过程为，先根节点即A，再左节点即B。目前遍历顺序：AB。此时以B为根节点的二叉树，先它的左节点即C，再它的右节点即D。目前遍历顺序：ABCD。此时以D为根节点的二叉树，由于它没有左节点，所以到它的右节点即E。目前遍历顺序：ABCDE。到现在整颗二叉树的根节点A，左节点B已经遍历完成，再到它的右节点即F。目前遍历顺序：ABCDF。此时以F为根节点的二叉树，先它的左节点即G。目前遍历顺序：ABCDFG。此时以G为根节点的，到它的右节点即H。最终遍历顺序为ABCDFGH。
中序遍历过程
中序遍历为CBDEAGHF
中序遍历过程为，先左节点即B，对于以B为根节点的二叉树，又要先它的左节点即C，以C为根节点的二叉树没有儿子节点，所以C是我们遍历到的第一个节点。目前遍历顺序：C。此时对于以B为根节点的二叉树，已经遍历完它的左节点，再到它的根节点即B。目前遍历顺序：CB。再到它的右节点D，以D为根节点的二叉树没有左节点，所以直接它的根节点D，再到它的右节点即E。目前遍历顺序：CBDE。现在整颗二叉树的左节点已经遍历完成，再到它的根节点A。目前遍历顺序：CBDEA。再到它的右节点F，但是以F为根节点的二叉树有左节点G，所以先它的左节点G，以G为根节点的二叉树没有左节点，所以先根节点G，再到右节点H。目前遍历顺序：CBDEAGH。此时以F为根节点的二叉树，它的左节点已经遍历完，再到它的根节点F。目前遍历顺序：CBDEAGHF。至此整颗二叉树遍历完成
后序遍历过程
后序遍历为CEDBHGFA
后序遍历过程为，先左节点即B，对于以B为根节点的二叉树，又要先它的左节点即C，以C为根节点的二叉树没有儿子节点，所以C是我们遍历到的第一个节点。目前遍历顺序：C。此时对于以B为根节点的二叉树，已经遍历完它的左节点，再到它的右节点即D。以D为根节点的二叉树没有左节点，所以到它的右节点即E。目前遍历顺序：CE。此时以D为根节点的二叉树右节点已经遍历完，再到它的根节点即D。目前遍历顺序：CED。此时以B为根节点的二叉树左节点右节点均已经遍历完，再到它的根节点即B。目前遍历顺序：CEDB。此时整颗二叉树的左节点已经遍历完成，再到它的右节点即F。此时以F为根节点的二叉树又要先它的左节点G，此时以G为根节点的二叉树没有左节点，所以先右节点即H，再遍历它的根节点即G。目前遍历顺序：CEDBHG。此时以F为根节点的二叉树，它的左节点已经遍历完成，同时没有右节点，所以到它的根节点即F。目前遍历顺序：CEDBHGF。此时整颗二叉树，它的左右节点均已遍历完成，所以到它的根节点A。最终遍历顺序为：CEDBHGFA。
解法1
回到这道题目，已知二叉树的前序中序遍历序列，要求重构二叉树。就以前序遍历{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6}构成的二叉树A为例来讲解解题思路。上面有提到前序遍历是先根节点再左右节点。所以已知A的前序遍历{1,2,4,7,3,5,6,8}，那么这颗二叉树的根节点一定是1。而中序遍历是先左节点，再根节点，再右节点。已知A中序遍历为{4,7,2,1,5,3,8,6}，且根节点是1。那么A的左节点是由1左边的中序序列{4,7,2}构成的二叉树A1，A的右节点是由1右边的中序序列{5,3,8,6}构成的二叉树A2。
因为A1的中序序列是{4,7,2}，元素个数是3，所以A的前序序列{1,2,4,7,3,5,6,8}中，根节点1后面的三个元素即{2,4,7}就是A1的前序序列。所以A2的前序序列就是{2,4,7}后面的所有元素，即{3,5,6,8}
到现在，我们已经把已知A的前序序列和中序序列求A的问题，转换为已知A1的前序中序序列求A1，已知A2的前序中序序列求A2的问题。继续递归下去，直到转换的子树前序中序序列只有一个元素，就可以直接表示出这颗子树了。
实现代码
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode (int x)
{
val = x;
}
}
public TreeNode reConstructBinaryTree(int[] pre, int[] tin)
{
if (!(pre.Length > 0))
{
return null;
}
TreeNode root = new TreeNode(pre[0]);
int index = -1;
// 找到在中序序列中根节点的位置
for (int i = 0; i < tin.Length; i ++)
{
if(tin[i] == pre[0])
{
index = i;
break;
}
}
// 利用根节点的位置，再求出左右两个子二叉树的前序中序序列
int[] subLeftPre = new int[index];
int[] subLeftTin = new int[index];
int[] subRightPre = new int[tin.Length - index - 1];
int[] subRightTin = new int[tin.Length - index - 1];
for (int j = 0; j < pre.Length; j ++)
{
if(j > 0)
{
if (j <= index)
{
subLeftPre[j - 1] = pre[j];
}
else
{
subRightPre[j - index - 1] = pre[j];
}
}
if (j < index)
{
subLeftTin[j] = tin[j];
}else if (j > index)
{
subRightTin[j - index - 1] = tin[j];
}
}
if(index > 0)
{
root.left = reConstructBinaryTree(subLeftPre, subLeftTin);
}
if (tin.Length - index - 1 > 0)
{
root.right = reConstructBinaryTree(subRightPre, subRightTin);
}
return root;
}
解法2
上面的解法1，是根据解题思路最直观的写法，但是写法很烂。由于C#对数组没有取子数组的API。所以求子二叉树的的前序中序序列写的太复杂了，需要自己去new前序中序数组，再往这些数组中填写正确的元素。后来是学习了别人的写法进行了优化。不用自己去创建子二叉树的前序中序数组，而是直接用父二叉树的前序中序序列索引来表示就可以了。
实现代码
public TreeNode reConstructSubTree(int[] pre, int p1, int p2, int[] tin, int t1, int t2)
{
if (p1 <= p2 && t1 <= t2 && p2 >= 0 && t2 >= 0)
{
TreeNode root = new TreeNode(pre[p1]);
for (int i = t1; i <= t2; i++)
{
if (tin[i] == pre[p1])
{
root.left = reConstructSubTree(pre, p1 + 1, p1 + i - t1, tin, t1, i - 1);
root.right = reConstructSubTree(pre, p1 + i + 1 - t1, p2, tin, i + 1, t2);
return root;
}
}
}
return null;
}
public TreeNode reConstructBinaryTreeOptimize(int[] pre, int[] tin)
{
return reConstructSubTree(pre, 0, pre.Length - 1, tin, 0, tin.Length - 1);
}
遇到的问题
在使用解法1解这个问题的时候，一直只能通过80%多的测试用例，花了很久的时间去查为什么。问题原因是由于希望提高效率，所以就在一个循环中构建出子二叉树的前序中序序列，但是逻辑上有bug，数组元素少赋值了，又由于新建的数组都是有默认值0的，导致序列实际上已经求解错误了，但又不易被发现。
递归问题是将大问题，转换为小问题，一直转换为小问题可以直接求解为止。我的这个bug其实并不是不容易被发现，直接代入最小问题就可以发现的，比如前序序列为{1, 2, 3}，中序序列为{2,1,3}。总结下来，以后对于递归问题，一定要先保证最小问题的解法是正确的，否则根基是错误的，最后得到的答案也一定是错误的。
最后放上有bug的代码，注意是有bug的
public TreeNode reConstructBinaryTree(int[] pre, int[] tin)
{
if (!(pre.Length > 0))
{
return null;
}
TreeNode root = new TreeNode(pre[0]);
int index = -1;
for (int i = 0; i < tin.Length; i ++)
{
if(tin[i] == pre[0])
{
index = i;
break;
}
}
int[] subLeftPre = new int[index];
int[] subLeftTin = new int[index];
int[] subRightPre = new int[tin.Length - index - 1];
int[] subRightTin = new int[tin.Length - index - 1];
// bug 这里j从1开始，会导致中序序列元素被少遍历一次，导致少赋值
for (int j = 1; j < pre.Length; j ++)
{
if (j <= index)
{
subLeftPre[j - 1] = pre[j];
}
else
{
subRightPre[j - index - 1] = pre[j];
}
if (j - 1 < index)
{
subLeftTin[j - 1] = tin[j - 1];
}else if (j - 1 > index)
{
subRightTin[j - 2 - index] = tin[index + j - 1 - index];
}
}
if(index > 0)
{
root.left = reConstructBinaryTree(subLeftPre, subLeftTin);
}
if (tin.Length - index - 1 > 0)
{
root.right = reConstructBinaryTree(subRightPre, subRightTin);
}
return root;
}
更多题目的完整描述，AC代码，以及解题思路请参考这里https://github.com/iwiniwin/Algorithm