python中如何遍历树

各种遍历顺序如下图所示：

树的深度

#classTreeNode(object):
#def__init__(self,x):
#self.val=x
#self.left=None
#self.right=None
classSolution(object):
defmaxdepth(self,root):
ifrootisNone:
return0
returnmax(self.maxdepth(root.left),self.maxdepth(root.right))+1

深度优先

深度优先遍历有三种方式：前序遍历、中序遍历和后序遍历

所说的前序、中序、后序，是指根节点的先后顺序。

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

#classTreeNode(object):
#def__init__(self,x):
#self.val=x
#self.left=None
#self.right=None
classSolution(object):
defpreorder(self,root):
ifrootisNone:
return''
printroot.val
ifroot.lef:
self.preorder(root.left)
ifroot.right:
self.preorder(root.right)

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

#classTreeNode(object):
#def__init__(self,x):
#self.val=x
#self.left=None
#self.right=None
classSolution(object):
defmidorder(self,root):
ifrootisNone:
return''
ifroot.lef:
self.midorder(root.left)
printroot.val
ifroot.right:
self.midorder(root.right)

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

#classTreeNode(object):
#def__init__(self,x):
#self.val=x
#self.left=None
#self.right=None
classSolution(object):
defendorder(self,root):
ifrootisNone:
return''
ifroot.lef:
self.endorder(root.left)
ifroot.right:
self.endorder(root.right)
printroot.val

广度优先

广度优先遍历，即层次遍历，优先遍历兄弟节点

层次遍历：根节点 -> 左节点 -> 右节点

#classTreeNode(object):
#def__init__(self,x):
#self.val=x
#self.left=None
#self.right=None
classSolution(object):
　　defgraorder(self,root):
　　　　ifrootisNone:
　　　　　　return''
　　　　queue=[root]
　　　　whilequeue:
　　　　　　res=[]
　　　　　　foriteminqueue:
　　　　　　　　printitem.val,
　　　　　　　　ifitem.left:
　　　　　　　　　　res.append(item.left)
　　　　　　　　ifitem.right:
　　　　　　　　　　res.apppend(item.right)
　　　　　　queue=res

比较两棵树是否相同

#classTreeNode(object):
#def__init__(self,x):
#self.val=x
#self.left=None
#self.right=None
classSolution(object):
defissame(self,root1,root2):
ifroot1isNoneandroot2isNone:
returnTrue
elifroot1androot2:
returnroot1.val==root2.valandissame(root1.left,root2.left)andissame(root1.right,root2.right)
else:
returnFalse

众多python培训视频，尽在python学习网，欢迎在线学习！