102.二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
题目链接

思路

递归法
根据题目要求，我们需要遍历二叉树，并将相同层次的节点归入同一个数组；
```
 可以通过传入辅助的level参数决定层次，就可以将同一level的放入同一数组。
```

迭代法（使用队列）
使用队列进行实现，弹出当前层节点的同时，依次加入下一层节点；由于队列先进先出的特性，当前层的节点会被先访问。

代码

Definition for a binary tree node.

class TreeNode(object):

 def __init__(self, val=0, left=None, right=None):
     self.val = val
     self.left = left
     self.right = right

class Queue(object):

 """实现一个队列"""
 
 def __init__(self):
     self.__list = []
 
 def enqueue(self, elem):
     """入队"""
     self.__list.append(elem)
 
 def dequeue(self):
     """出队"""
     return self.__list.pop(0)
 
 def is_empty(self):
     return not self.__list
 
 def size(self):
     """队列的大小"""
     return len(self.__list)

class Solution(object):

 def levelOrder(self, root):
     """使用队列对树进行层序遍历，无返回值"""
     if not root:
         return
     queue = Queue()
     queue.enqueue(root)
     while queue.size() != 0:
         node = queue.dequeue()
         print(node.val)
         if node.left is not None:
             queue.enqueue(node.left)
         if node.right is not None:
             queue.enqueue(node.right)
 
 def levelOrder1(self, root):
     """
     递归法
     
     根据题目要求，我们需要遍历二叉树，并将相同层次的节点归入同一个数组；
     可以通过传入辅助的level参数决定层次，就可以将同一level的放入同一数组。
     """
     def helper(node, level):
         if len(levels) == level:  # 每一层都需要创建一个数组
             levels.append([])
         
         levels[level].append(node.val)  # 向对应层的数组中加入节点
         
         # 递归，层次+1
         if node.left is not None:
             helper(node.left, level + 1)
         if node.right is not None:
             helper(node.right, level + 1)
     
     levels = []
     if root is None:
         return levels
     helper(root, 0)
     return levels
 
 def levelOrder2(self, root):
     """
     迭代法
     
     使用队列进行实现，弹出当前层节点的同时，依次加入下一层节点；由于队列先进先出的特性，当前层的节点会被先访问。
     """
     answer = []
     level = []
     dummy = TreeNode(1001)
     queue = Queue()
     
     if not root:
         return answer
     
     queue.enqueue(root)
     queue.enqueue(dummy)
     
     while not queue.is_empty():
         current = queue.dequeue()
         if current == dummy:
             answer.append(level)
             level = list()
             if not queue.is_empty():
                 queue.enqueue(dummy)
         else:
             level.append(current.val)
             if current.left is not None:
                 queue.enqueue(current.left)
             if current.right is not None:
                 queue.enqueue(current.right)
     
     return answer

if name == “main“:

 # create the binary tree
 root = TreeNode(3)
 node2 = TreeNode(9)
 node3 = TreeNode(20)
 node4 = TreeNode(15)
 node5 = TreeNode(7)
 root.left = node2
 root.right = node3
 node3.left = node4
 node3.right = node5
 
 slt = Solution()
 # slt.levelOrder(root)
 # res = slt.levelOrder1(root)
 res = slt.levelOrder2(root)
 print(res)

victory的博客

leetcode | 102.二叉树的层序遍历

102.二叉树的层序遍历

题目描述

思路

代码

Definition for a binary tree node.