二叉树及遍历
二叉树概念
二叉树是有限个元素的集合，该集合或者为空、或者有一个称为根节点（root）的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。
#python实现二叉树的构建
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
构建的二叉树如图：
下面二叉树的各种遍历也基于这个图进行。
二叉树的遍历及python实现
二叉树的遍历
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问且仅被访问一次。从而有：
- 前序遍历：先输出根节点，再依次前序遍历左子树和右子树。
- 中序遍历：先中序遍历左子树，再输出根节点，最后中序遍历右子树。
- 后序遍历：先后序遍历左子树，接着后序遍历右子树，最后输出根节点。
- 层次遍历：从上往下、从左至右依次打印树的节点。
python实现
从二叉树的构建及二叉树的遍历我们可以看出其中都蕴含着“递归”的思想，因此今天我们主要用递归来实现二叉树的遍历。
#前序遍历
def preTraverse(root):
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
#中序遍历
def midTraverse(root):
if root==None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
#后序遍历
def afterTraverse(root):
if root==None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
leetcode107题python实现
题目描述
python实现
def levelOrderBottom(root):
if not root:
return []#为空则返回空列表
queue=[root]#使用列表实现队列的功能，首先存储root
res=[]
while queue:#当queue不为空时
nodes=[]#存节点，每次循环前置空，每次只装一部分
node_values=[]#存节点的值
for node in queue:
if node.left:
nodes.append(node.left)#将左子树装入队列中
if node.right:
nodes.append(node.right)
node_values+=[node.value]#因为每次循环node_values都会置空，所以最终结果保存在res里，node_values只是一小部分结果
res=[node_values]+res#实现从底到顶，node_values放前面.
queue=nodes#将新添加的节点重新赋值给queue
return res