剑指offer-32.从上到下打印二叉树（层次遍历/广度优先搜索）★

本文主要是介绍剑指offer-32.从上到下打印二叉树（层次遍历/广度优先搜索）★，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/ （按层输出）

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/ （之字形按层输出）

思路：

深度优先搜索利用栈先入后出的特点，广度优先搜索利用队列先入先出的特点。

代码：

其实就是先序遍历，只是pop出来的是队列的第一个元素。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []res = []q = [root]        # 队列while q:node = q.pop(0)      # 与先序遍历的区别只在这一行，每次取队列的第一个元素res.append(node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)return res        

如果要求一层输出一行，就多一个内循环，每次在队列尾部加上当前节点的左右子树：

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []res = []q = [root]while q:tmp = []for i in range(len(q)):        node = q.pop(0)tmp.append(node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)res.append(tmp)return res

如果要求之字形按层输出，增加一个标志或是根据res里的项数来判断当前是奇数层还是偶数层：

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []res = []q = [root] flag = 1while q:tmp = []for i in range(len(q)):node = q.pop(0)tmp.append(node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)res.append(tmp if flag==1 else tmp[::-1])     # flag为1表示奇数层，否则为偶数层flag *= -1     # 反转一下return res

 

这篇关于剑指offer-32.从上到下打印二叉树（层次遍历/广度优先搜索）★的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---