code4offer-5

重建二叉树

问题描述

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

分析

前序遍历序列第一个元素是树的root
从中序遍历序列中找到pre[0]，pre[0]的左边是树的左子树，右边是右子树

在前序遍历序列中，左子树序列中第一个元素是左子树的根，右子树同理

用递归的思想重建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def reConstructBinaryTree(self, pre, tin):
    if (len(pre) == 0):
        return None
    if (len(pre) == 1):
        return TreeNode(pre[0])
    root = TreeNode(pre[0])
    left = 0

    for i in tin:
        if i != pre[0]:
            left = left + 1
        else:
            break

    root.left = self.reConstructBinaryTree(pre[1:left+1], tin[0:left])
    root.right = self.reConstructBinaryTree(pre[left+1:], tin[left+1:])

    return root