剑指offer面试题：重建二叉树

题目描述

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

思路分析

根节点肯定是前序遍历的第一个数。找到中序遍历根节点所在位置。
对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边。利用上述这点，对二叉树节点进行归并。
取出前序和中序遍历根节点左边和右边的子树递归，再对其进行上述所有步骤（递归），即再区分子树的左、右子子数，直到叶节点。

Python的解法简洁明了。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here

        if not pre or not tin:
            return None
        root = TreeNode(pre.pop(0))
        index = tin.index(root.val)
        root.left = self.reConstructBinaryTree(pre, tin[:index])
        root.right = self.reConstructBinaryTree(pre, tin[index + 1:])
        return root

这是C++的解法，一样的思路。

/* 先序遍历第一个位置肯定是根节点node，
 
  中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组
 
  另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组
 
  把四个数组找出来，分左右递归调用即可。
*/
 
class Solution {
 
public:
 
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
 
        int in_size = in.size();
        if(in_size == 0)
            return NULL;
        vector<int> pre_left, pre_right, in_left, in_right;
        //创建根节点，根节点肯定是前序遍历的第一个数
        int val = pre[0];
        TreeNode* node = new TreeNode(val);//root node is the first element in pre
        //找到中序遍历根节点所在位置,存放于变量p中
        int p = 0;
        for(p; p < in_size; ++p){
            if(in[p] == val) //Find the root position in in
                break;
        }
 		//对二叉树节点进行归并
        for(int i = 0; i < in_size; ++i){
            if(i < p){
                in_left.push_back(in[i]);//Construct the left pre and in 
                pre_left.push_back(pre[i+1]);
            }
            else if(i > p){
                in_right.push_back(in[i]);//Construct the right pre and in 
                pre_right.push_back(pre[i]);
            }
        }
 		//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
        node->left = reConstructBinaryTree(pre_left, in_left);
        node->right = reConstructBinaryTree(pre_right, in_right);
 
        return node;
 
    }
};