【算法日常】二叉树的层级遍历

　　

二叉树的层次遍历

　　

题目力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
【算法日常】二叉树的层级遍历

　　

题解:

　　

本题有两种解法,首先第一种肯定是非常明显的广度优先遍历,另一种深度优先遍历的解法。

　　
第一种:广度优先遍历h5> 　　
　　

广度优先遍历,将遍历的每层的结果放入一个列表中,该层遍历结束,将整个结果列表加入到总的结果中即可。
时间复杂度<强> O (n) 空间复杂度<强> O(1) (结果的存储空间若不进行计算的话)

　　 　　 　　

<强>代码如下:

　　
 <代码类="语言python ">导入收藏
　　
　　类TreeNode:
　　def __init__(自我,val):
　　自我。val=val
　　自我。左=自我。正确的=没有
　　
　　#广度优先遍历方法
　　def level_order(根:TreeNode)→列表:
　　如果不是根:
　　返回[]
　　
　　队列=collections.deque() #申请一个双端队列
　　queue.append(根)
　　结果=[]
　　
　　#访问=集(根)#因为是树的结构,所以只要向下走不会存在重复的情况
　　
　　而队列:
　　level_size=len(队列)
　　current_level=[]
　　
　　在范围(level_size): _
　　节点=queue.popleft() #这里从左边出了,下面加入的时候就要加到末尾,若是从右边出,则下面从左边进推去
　　current_level.append (node.val)
　　
　　如果node.left:
　　queue.append (node.left)
　　如果node.right:
　　queue.append (node.right)
　　result.append (current_level)
　　返回结果
　　
　　if __name__==癬_main__”:
　　node1=TreeNode (1)
　　node2=TreeNode (2)
　　node3=TreeNode (3)
　　node4=TreeNode (4)
　　node5=TreeNode (5)
　　node6=TreeNode (6)
　　node7=TreeNode (7)
　　
　　node4。左=node2
　　node2。左=node1
　　node2。正确的=node3
　　node4。正确的=node6
　　node6。左=node5
　　node6。正确的=node7
　　打印(level_order (node4)
　　

<强>输出结果:

　　
 <代码类=" language-bash ">[[4],[2,6],[1、3、5、7]]
　　
第二种解法:深度优先遍历h5> 　　
　　

进行深度遍历,将没个遍历的节点,加入到每一层对应的结果里面
时间复杂度<强> O (n) 空间复杂度<强> O(1) (结果的存储空间若不进行计算的话)

　　 　　 　　

__代码如下:___

　　
 <代码类="语言python ">类TreeNode:
　　def __init__(自我,val):
　　自我。val=val
　　自我。左=自我。正确的=没有
　　
　　#依靠深度优先遍历的算法
　　def level_order(根:TreeNode)→列表:
　　如果不是根:
　　返回[]
　　
　　结果=[]
　　level_size=0
　　结果=depth_first_search(根、level_size、结果)
　　返回结果
　　
　　def depth_first_search(根、水平、结果):
　　如果不是根:
　　返回[]
　　
　　如果len(结果)& lt;级+ 1:
　　result.append ([])
　　
　　结果(水平).append (root.val)
　　depth_first_search(根。左,等级+ 1,结果)
　　depth_first_search(根。级+ 1,结果)
　　返回结果
　　
　　if __name__==癬_main__”:
　　node1=TreeNode (1)
　　node2=TreeNode (2)
　　node3=TreeNode (3)
　　node4=TreeNode (4)
　　node5=TreeNode (5)
　　node6=TreeNode (6)
　　node7=TreeNode (7)
　　
　　node4。左=node2
　　node2。左=node1
　　node2。正确的=node3
　　node4。正确的=node6
　　node6。左=node5
　　node6。正确的=node7
　　print (level_order (node4))
　　
　　

<强>输出结果:

　　
 <代码类=" language-bash ">[[4],[2,6],[1、3、5、7]]

【算法日常】二叉树的层级遍历