题干：输入某二叉树的前序遍历和中虚遍历的结果，请重建出该二叉树。假设输入的前序遍历和中虚遍历的结果中都不含重复的数字。例如，输入前序遍历序列{，1，2，4，7，3，5，6，8 }和中虚遍历序列{4，7，2，1，5，3，8，6},则重建出如下图所示的二叉树并输出它的头结点。
解题思路：
我们知道二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树结点的值位于根结点的值的右边。因此我们可以扫描中序遍历 序列找到根结点的值。
前序遍历序列的第一个数字1就是根结点的值，在扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。
既然我们都已经分别找到了左右子树的前序遍历序列和中序遍历序列，我门可以用同样的办法分别去构建左右子树。也就是说接下来的事情可以用递归的方法去完成。
实现代码：
#include <stdio.h> #include <stdlib.h> struct BinaryTreeNode { int m_nValue; struct BinaryTreeNode * m_pLeft; struct BinaryTreeNode * m_pRight; }; struct BinaryTreeNode * constructCore (int * startPreorder,int *endPreorder,int * startInorder,int * endInorder) { int rootValue = startPreorder[0]; struct BinaryTreeNode * root = malloc(sizeof(struct BinaryTreeNode)); root->m_nValue = rootValue; root->m_pLeft = NULL; root->m_pRight = NULL; if (startPreorder == endPreorder) { if (startInorder == endInorder && *startPreorder == * startInorder) { return root; } else { return NULL; //非法输入 } } int * rootInorder = startInorder; while (rootInorder<= endInorder && *rootInorder != rootValue) { //指针＋ －> 地址＋ rootInorder++; } if (rootInorder == endPreorder && * rootInorder != rootValue) { return NULL; //非法输入 } long int leftLength = rootInorder - startInorder; int * leftPreorderEnd = startPreorder + leftLength; if (leftLength > 0) { root->m_pLeft = constructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1); } if (leftLength < endPreorder - startPreorder) { root->m_pRight = constructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endPreorder); } return root; } struct BinaryTreeNode * construct(int * preorder,int * inorder,int length) { if (preorder == NULL || inorder == NULL || length <=0) { return NULL; } return constructCore(preorder, preorder + length - 1, inorder, inorder + length - 1); } int main(int argc, const char * argv[]) { // insert code here... printf("Hello, World!\n"); int a[8] = {1,2,4,7,3,5,6,8}; int b[8] = {4,7,2,1,5,3,8,6}; construct(a,b,8); return 0; } class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def __init__(self): self.dic = {} self.po = [] # 做好递归前的基本条件 def buildTree(self, preorder: list, inorder: list) -> TreeNode: self.dic = {} self.po = preorder for i in range(len(inorder)): self.dic[inorder[i]] = i return self.recur(0, 0, len(inorder) - 1) # pre_root是先序遍历的下标 in_left是中序遍历下标 in_right是后序遍历索引 def recur(self, pre_root, in_left, in_right): if in_left > in_right: return # 终止条件：中序遍历为空 root = TreeNode(self.po[pre_root]) # 建立当前子树的根节点 i = self.dic[self.po[pre_root]] # 搜索根节点在中序遍历中的索引，从而可对根节点、左子树、右子树完成划分。 root.left = self.recur(pre_root + 1, in_left, i - 1) # 开启左子树的下层递归 root.right = self.recur(i - in_left + pre_root + 1, i + 1, in_right) # 开启右子树的下层递归 return root # 返回根节点，作为上层递归的左（右）子节点 preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] solu = Solution() tree = solu.buildTree(preorder, inorder) print(tree)
