本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考，具体如下：二叉
本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考，具体如下：
二叉树的定义：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
二叉树的前序遍历
递归
def preorder(root,res=[]):
if not root:
return
res.append(root.val)
preorder(root.left,res)
preorder(root.right,res)
return res
迭代
def preorder(root):
res=[]
if not root:
return []
stack=[root]
while stack:
node=stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node,left)
return res
二叉树的中序遍历
递归
def inorder(root,res=[]):
if not root:
return
inorder(root.left,res)
res.append(root.val)
inorder(root.right,res)
return res
迭代
def inorder(root):
stack=[]
node=root
res=[]
while stack or node:
while node:
stack.append(node)
node=node.left
node=stack.pop()
res.append(node.val)
node=node.right
return res
二叉树的后序遍历
递归
def laorder(root,res=[]):
if not root:
return
laorder(root.left,res)
laorder(root.right,res)
res.append(root.val)
return res
迭代
def laorder(root):
stack=[root]
res=[]
while stack:
node=stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
二叉树的层次遍历
迭代
def levelorder(root):
queue=[root]
res=[]
while queue:
node=queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(node.val)
return res