您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍了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中遍历树的方法有哪些内容对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,遇到问题就找亿速云,详细的解决方法等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。