剑指剑指Offer 04 – 重建二叉树详解重建二叉树详解(Python版版)
题目描述题目描述:
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返
回。
什么是二叉树什么是二叉树?
二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有
序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
二叉树的遍历二叉树的遍历
遍历 ：沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。
遇到没遍历的新节点都当根处理
先序遍历： 先访问树根，再访问左子树，最后访问右子树；根左右
中序遍历： 先访问左子树，再访问树根，最后访问右子树；左根右
后序遍历： 先访问左子树，再访问右子树，最后访问树根；左右根
层次遍历: 从根节点开始，逐层从左向右进行遍历。
使用使用Python实现二叉树实现二叉树
# 二叉树节点
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 二叉树操作
class Bitree:
def __init__(self, root=None):
self.root = root # 获取树根
# 先序遍历
def preOrder(self,node):
# 传入根节点
if node is None:
return
# 打印根节点数据
print(node.val,end=' ')
# 将根节点的左点节 作为根节点 递归调用自身，直至满足node is None，停止递归
self.preOrder(node.left)
self.preOrder(node.right)
# 中序遍历
def inOrder(self, node):
if node is None:
return
self.inOrder(node.left)
print(node.val, end=' ')
self.inOrder(node.right)
# 后序遍历
def postOrder(self, node):
if node is None:
return
self.postOrder(node.left)
self.postOrder(node.right)
print(node.val, end=' ')
if __name__ == "__main__":
# 后序遍历 ＢＦＧＤＩＨＥＣＡ
# 构建树
b = TreeNode('B')
f = TreeNode('F')
g = TreeNode('G')
d = TreeNode('D', f, g)
i = TreeNode('I')
h = TreeNode('H')
e = TreeNode('E', i, h)
c = TreeNode('C', d, e)
a = TreeNode('A', b, c) # 树根
# 初始化树对象，得到树根
bt = Bitree(a)
# 先序
bt.preOrder(bt.root)
print()
# 中序
bt.inOrder(bt.root)
print()
评论0