【leetcode系列】【算法】【中等】二叉树的层序遍历(stack、DFS)
程序员文章站
2022-07-07 18:56:41
...
题目:
题目链接: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
解题思路:
方法一:栈(时间O(N),空间O(N))
变量:
- stack : 遍历时的栈,初始化时,只将根节点放入
- res : 结果集
- val_lst : 当前需要加入到结果集的list
流程:
初始化stack时,将root节点3放入到stack中,然后开始遍历:
获取栈的第一个元素,放入到val_lst中,此时发现并将3的左右子树放入到stack中
并且此时已遍历完本次遍历开始是stack中的所有元素,退出本次遍历,将val_lst中的值放入到res中:
继续开始遍历,获取栈中的第一个元素2,将2放入到val_lst中并出栈,然后将2的左右子树入栈:
继续将9放入到val_lst中,将9出栈,因为9没有左右子树,不需要将栈中新增元素
此时已遍历完本次需要遍历的所有元素,退出本次遍历,将val_lst加入到结果集res中,继续下一次遍历:
继续遍历,直到stack中为空
方法二:DFS(时间O(N),空间O(N))
DFS搜索,添加一个层级标记,标识当前值需要加入到哪一层的结果中
代码实现:
方法一:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
stack = [root]
res = []
while stack:
val_lst = []
for index in range(0, len(stack)):
node = stack[0]
stack.pop(0)
val_lst.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(val_lst)
return res
方法二:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
def create_res(res, node, level):
print(res)
if not node:
return res
if len(res) == level:
res.append([])
res[level].append(node.val)
if node.left:
create_res(res, node.left, level + 1)
if node.right:
create_res(res, node.right, level + 1)
return res
return create_res([], root, 0)