Python-剑指offer(4)重建二叉树

简介: Python-剑指offer(4)重建二叉树

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


环境Python2.7.3


二叉树遍历的规则


前序遍历的规则:

(1)访问根节点

(2)前序遍历左子树

(3)前序遍历右子树


中序遍历的规则:

(1)中序遍历左子树

(2)访问根节点

(3)中序遍历右子树


后序遍历二叉树的规则:

(1)后序遍历左子树

(2)后序遍历右子树

(3)访问根节点


解析:根据前序遍历二叉树的规则可知前序遍历结果的第一个元素即为整个二叉树的根节点,知道了根节点之后,根据中序遍历的组成结构我们可以知道左子树和右子树所含元素,对左右子树递归调用二叉树重建函数,最后即可返回整个重建后的二叉树。

# -*- 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
        else:
            root = TreeNode(pre[0])
            for i in range(len(tin)):
                if tin[i] == pre[0]:
                    break
            root.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i])
            root.right = self.reConstructBinaryTree(pre[i+1:],tin[i+1:])
        return root


相关文章
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
51 6
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
43 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 04. 二维数组中的查找
剑指Offer题目 "二维数组中的查找" 的Python解决方案,包括非递归迭代、递归以及使用内置函数的二分查找方法,以判断一个有序的二维数组中是否含有给定整数。
34 1
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
34 1
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
48 7
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
23 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
48 5
|
3月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
21 3
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - II. 从上到下打印二叉树 II
本文提供了一种Python实现方法,用于层次遍历二叉树并按层打印结果,每层节点按从左到右的顺序排列,每层打印到一行。
34 3
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
Leetcode题目"剑指 Offer 21. 调整数组顺序使奇数位于偶数前面"的两种Python解决方案,一种是使用双端队列调整数组顺序,另一种是使用双指针法将奇数移到数组前半部分,偶数移到后半部分。
26 4