面试题7：重建二叉树

题目描述

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

知识点

二叉树的遍历

Qiang的思路

对于二叉树，遍历是最基本的东西，先序遍历是指先遍历根节点，然后左子树，最后右子树；中序遍历是指先左子树，然后根节点，最后右子树。

所以能够发现，先序遍历序列中的第一个元素必然是整个二叉树的根节点，比如：{1,2,4,7,3,5,6,8}中1是整个二叉树的根节点，但是其后面的元素{2,4,7,3,5,6,8}哪些是左子树哪些是右子树就无法得知了。

这是考虑中序遍历，因为1是整个二叉树的根节点，它在中序遍历中恰恰是左右子树划分的节点，所以能够得到左子树{4,7,2}和右子树{5,3,8,6}。以左子树为例，其先序遍历序列应该就是4,7,2在整个二叉树的先序遍历序列中的结果，即{2,4,7}，其中序遍历结果为{4,7,2}。

按照这个思路便可以继续寻找左子树和右子树的根节点并对其进行下一步分左子树和右子树划分，直到叶子结点为止，便可以重构这个二叉树了。

# -*- 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 None
        root=pre[0]
        tree=TreeNode(root)
        if len(pre)==1:
            return tree
        index=tin.index(root)
        tree.left=self.reConstructBinaryTree(pre[1:index+1],tin[:index])
        tree.right=self.reConstructBinaryTree(pre[index+1:],tin[index+1:])
        return tree

Book中的思路

自己的做法和书中提及的做法相同，采用递归的方式实现，简单清晰。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。