剑指Offer编程题-重建二叉树 | 我的个人生活记录

题目：重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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是根结点，在中序序列中，{4,7,2}和{5,3,8,6}是被根节点1划分的两个部分，且分别对应于整棵树的左子树和右子树。将左子树和右子树分别看作两棵完整的树，使用递归继续划分就可重建出整棵二叉树。

实现

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:
            node = TreeNode(pre[0])
            # 根节点在中序序列中的位置
            index = tin.index(pre[0])
            if len(pre[1:index+1])>0:
                node.left = self.reConstructBinaryTree(pre[1:index+1], tin[0:index])
            if len(pre[index+1:])>0:
                node.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
            return node
        else:
            return None

讨论区大神的简洁版（每一次处理左子树时都将节点pop掉）：

# -*- 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

补充内容

二叉树的遍历方式：

• 先序遍历：根节点->左子树->右子树

• 中序遍历：左子树->根节点->右子树

• 后序遍历：左子树->右子树->根节点

代码实现（上文题目的验证过程）：

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


# 先序遍历
def preorderTraversal(node):
    if node != None:
        print(node.val)
    if node.left != None:
        preorderTraversal(node.left)
    if node.right != None:
        preorderTraversal(node.right)


# 中序遍历
def inorderTraversal(node):
    if node.left != None:
        inorderTraversal(node.left)
    if node != None:
        print(node.val)
    if node.right != None:
        inorderTraversal(node.right)


# 后序遍历
def postorderTraversal(node):
    if node.left != None:
        postorderTraversal(node.left)
    if node.right != None:
        postorderTraversal(node.right)
    if node != None:
        print(node.val)


pre = [1,2,4,7,3,5,6,8]
tin = [4,7,2,1,5,3,8,6]
node = Solution().reConstructBinaryTree(pre, tin)
print('pre:')
preorderTraversal(node)
print('in:')
inorderTraversal(node)
print('post:')
postorderTraversal(node)