创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商,新人活动买多久送多久,划算不套路!
站在用户的角度思考问题,与客户深入沟通,找到河池网站设计与河池网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站设计、成都网站建设、企业官网、英文网站、手机端网站、网站推广、申请域名、虚拟空间、企业邮箱。业务覆盖河池地区。这篇文章主要介绍了python中遍历树的方法有哪些,具有一定借鉴价值,需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获。下面让小编带着大家一起了解一下。
各种遍历顺序如下图所示:
树的大深度
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxdepth(self, root): if root is None: return 0 return max(self.maxdepth(root.left), self.maxdepth(root.right))+1
深度优先
深度优先遍历有三种方式:前序遍历、中序遍历和后序遍历
所说的前序、中序、后序,是指根节点的先后顺序。
前序遍历:根节点 -> 左子树 -> 右子树
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def preorder(self, root): if root is None: return '' print root.val if root.lef: self.preorder(root.left) if root.right: self.preorder(root.right)
中序遍历:左子树 -> 根节点 -> 右子树
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def midorder(self, root): if root is None: return '' if root.lef: self.midorder(root.left) print root.val if root.right: self.midorder(root.right)
后序遍历:左子树 -> 右子树 -> 根节点
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def endorder(self, root): if root is None: return '' if root.lef: self.endorder(root.left) if root.right: self.endorder(root.right) print root.val
广度优先
广度优先遍历,即层次遍历,优先遍历兄弟节点
层次遍历:根节点 -> 左节点 -> 右节点
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def graorder(self, root): if root is None: return '' queue = [root] while queue: res = [] for item in queue: print item.val, if item.left: res.append(item.left) if item.right: res.apppend(item.right) queue = res
比较两棵树是否相同
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def issame(self, root1, root2): if root1 is None and root2 is None: return True elif root1 and root2: return root1.val==root2.val and issame(root1.left, root2.left) and issame(root1.right, root2.right) else: return False
感谢你能够认真阅读完这篇文章,希望小编分享python中遍历树的方法有哪些内容对大家有帮助,同时也希望大家多多支持创新互联,关注创新互联-成都网站建设公司行业资讯频道,遇到问题就找创新互联,详细的解决方法等着你来学习!