一道编程题——重建二叉树

题目描述

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

题目分析

根据二叉树的前序遍历和中序遍历重建二叉树，或者计算后序遍历是二叉树的基础操作。

前序遍历是指先根节点，再左右子节点；中序遍历是指先左子节点，再根节点，最后右子节点；后续遍历是指先左右子节点，再根节点。

前序遍历和中序遍历可以唯一确定一棵二叉树，所以后序遍历的结果是唯一的。

一般遇到这样的问题，首选 递归 的方法。

解题思路

由于前序遍历是先根节点，后子节点，中序遍历为先左后跟。所以结合二者，对于前序遍历的结果，第一位必然是树的根，并且根据这个根，我们可以在中序遍历中找到左子树（根前面的元素）。

例如题目中的前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。

可知，前序遍历第一位为1，则1为树根，而在中序中1前面的都是左子树，所以左子树为4，7，2.

那么，我们就可以把前序和中序遍历划分为根，左子树，右子树。

前序：｛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 len(pre) == 0: return 
        # 根节点为前序遍历的第一个节点
        root = TreeNode(pre[0])
        # 因为不含重复的数字，所以可以直接使用列表的index方法
        # 这里需要注意对于原前序和中序列表的截取
        root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1], tin[:tin.index(pre[0])])
        root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:])
        return root

C++实现

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int p_size = pre.size();
        if (p_size ==0)
            return NULL;
        vector<int> pre_left, pre_right, vin_left, vin_right;
        int val = pre[0];
        TreeNode* root = new TreeNode(val);
        // 寻找根节点在中序遍历中的位置
        int p =0;
        for(p; p < p_size; p++){
            if(vin[p] == val)
                break;
        }
        // 根据根节点在中序遍历中的位置，分为左子树和右子树
        for(int i=0; i < p_size; i++){
            if(i < p){ 
                //左子树
                // 前序遍历的第一个元素是根节点，后面是左子树和右子树，所以从1开始
                pre_left.push_back(pre[i+1]);
                vin_left.push_back(vin[i]);
            }
            else if(i > p){ 
                //右子树
                pre_right.push_back(pre[i]);
                vin_right.push_back(vin[i]);
            }
        }
        // 递归左右子树
        root->left = reConstructBinaryTree(pre_left, vin_left);
        root->right = reConstructBinaryTree(pre_right, vin_right);
        
        return root;
    }
};