面试题----重建二叉树

一、题目：输入某二叉树的前序遍历和中序遍历的结果，重建出该二叉树，假设无重复数字。例如前序遍历结果为{1，2，4，7，3，5，6，8}，中序遍历结果为{4，7，2，1，5，3，8，6}，重建出该二叉树并输出其头节点。

首先看到该题目，我们心里应该清楚二叉树的前序遍历和中序遍历各自有什么特点，想不通的话可以在纸上画一画。前序遍历序列中第一个数字总是该二叉树的根节点，但是在中序遍历序列中根节点在中间，结合两个序列，我们很容易就能知道二叉树的根节点以及左右子树，如下图所示： 依照这种方法，第二遍查找根节点为2，那么在左子树中（中序遍历序列）可以发现2只有左子树，接着根节点为4时，右子树是7......按照这种思路就可以将一棵完整的二叉树重构出来了，不难发现，这里用了一种递归的思路，重建的二叉树如下所示：建议在纸上画一画 在了解整棵树如何重构之后，算法代码也就很容易能够写出来了，就是递归方法的一种实现 二叉树节点定义： struct BinaryTreeNode { int value; BinaryTreeNode* pLeft; //左节点 BinaryTreeNode* pRight; //右节点 }; 递归代码如下： BinaryTreeNode* RebuildCore(int *startPreorder,int *endPreorder,int *startInorder,int *endInorder) { int rootValue = startPreorder[0]; BinaryTreeNode* root =new BinaryTreeNode(); root->value = rootValue; root->pLeft = root->pRight = NULL; //判断前序和中序遍历中是不是只有一个节点，若是则该树就只有一个节点即根 if(startPreorder == endPreorder) { if(startInorder == endInorder && *startPreorder == *startInorder) { return root; } else { throw std::exception("invailed input"); } } //在中序遍历中找到根节点 int *rootInorder = startInorder; while (rootInorder <= endInorder && *rootInorder != rootValue) { rootInorder++; } if (rootInorder == endInorder && *rootInorder != rootValue) { throw std::exception("invailed input"); } int leftLength = rootInorder - startInorder; int *leftInorderNow = startPreorder + leftLength; //构建左子树 if(leftLength > 0) { root->pLeft = RebuildCore(startPreorder+1,leftInorderNow,startInorder,rootInorder-1); } //构建右子树 if(leftLength < endPreorder - startPreorder) { root->pRight = RebuildCore(leftInorderNow+1,endPreorder,rootInorder+1,endInorder); } return root; } BinaryTreeNode* Rebuild(int *preorder,int *inorder,int length) { if (preorder == NULL || inorder == NULL || length < 0) { return NULL; } return RebuildCore(preorder,preorder+length-1,inorder,inorder+length-1); } 参考剑指offer上的面试题，以上就是大概的思路，感受最深的是在写代码之前一定要先整理好自己的思路，不要一上来就开始写，就想着我要实现这个功能，先把思路整理好，代码实现就是将自己的思路用另外一种语言呈现出来罢了，所以，思路很重要。没有思路的话，在纸上画一画，想一想，这个问题还能不能拆分成一些更小的自己能够解决的一些问题，然后再整合，解决一个大问题。