【面试题6】重建二叉树

【题目描述】

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

【解决方案】

首先理解前序遍历（PreOrder），中序遍历（InOrder），后序遍历（PostOrder）的区别，并能在纸上根据前两种遍历，写出后一种遍历，基本就能写出本题的代码，不赘述。

我的代码实现，仅供参考：

 1         /// <summary>
 2         /// 根据前序遍历和中序遍历构建二叉树
 3         /// </summary>
 4         /// <param name="preOrder"></param>
 5         /// <param name="inOrder"></param>
 6         /// <returns></returns>
 7         public static BinaryTreeNode ConstructBT(
 8             int[] preOrder, int[] inOrder,
 9             int startPre, int endPre,
10             int startIn, int endIn)
11         {
12             int rootValue = preOrder[startPre];
13             int rootIndexIn = Array.IndexOf(inOrder, rootValue);
14             int leftLength = rootIndexIn - startIn;
15             int rightLength = endIn - rootIndexIn;
16 
17             BinaryTreeNode root = new BinaryTreeNode(rootValue);
18 
19             if(leftLength>0)
20             { 
21                 root.Left = ConstructBT(
22                     preOrder, inOrder,
23                     startPre + 1, startPre + leftLength,
24                     startIn, rootIndexIn - 1);
25             }
26 
27             if(rightLength>0)
28             { 
29                 root.Right = ConstructBT(
30                     preOrder, inOrder,
31                     startPre + leftLength + 1, endPre,
32                     rootIndexIn + 1, endIn);
33             }
34 
35             return root;
36         }