本文主要是介绍Leetcod面试经典150题刷题记录 —— 二叉树层次遍历篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Leetcod面试经典150题刷题记录-系列 |
|---|
| Leetcod面试经典150题刷题记录——数组 / 字符串篇 |
| Leetcod面试经典150题刷题记录 —— 双指针篇 |
| Leetcod面试经典150题刷题记录 —— 矩阵篇 |
| Leetcod面试经典150题刷题记录 —— 滑动窗口篇 |
| Leetcod面试经典150题刷题记录 —— 哈希表篇 |
| Leetcod面试经典150题刷题记录 —— 区间篇 |
| Leetcod面试经典150题刷题记录——栈篇 |
| Leetcod面试经典150题刷题记录——链表篇 |
| Leetcod面试经典150题刷题记录——二叉树篇 |
| Leetcod面试经典150题刷题记录——二叉树层次遍历篇 |
| Leetcod面试经典150题刷题记录——二叉搜索树篇 |
二叉树层次遍历篇
- 1. 二叉树的右视图
- 2. 二叉树的层平均值
- 3. 二叉树的层序遍历
- 4. 二叉树的锯齿形层序遍历
在二叉树的传统里，用p指代左子树，用q指代右子树，这个原因是为什么呢？我以为，将pq两个字母里的圈圈视作节点，p那一撇就是左子树的延伸，q那一捺就是右子树的延伸，所以其实是按象形的意义来命名的，这比left和right还要直观，因此，bd也可以认为是倒过来的二叉树的表示法。
1. 二叉树的右视图
题目链接：二叉树的右视图 - leetcode
题目描述：
给定一个二叉树的 根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
题目归纳：
右视图 = 右边的侧视图
解题思路：
解法： 二叉树的右视图 - leetcode官方题解
(1) 从左到右层序遍历。记录层序遍历的最后一个node，即为右视图看到的第一个node。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]: rightmost_value_at_depth = dict() max_depth = -1# deque 数据类型来自于collections 模块，支持从头和尾部的常数时间 append/pop 操作。# deque([1,2,3]) 的用法类似于 list([1,2,3])# 非传统层序遍历写法，只有1层循环，缺点是层和层界限不清，优点是写起来快queue = deque( [(root,0)] ) # deque = double-ended queue，双向队列。该队列的最小单元是(node,node_depth)while queue:node, depth = queue.popleft() # 若使用 Python 的 list，通过 list.pop(0) 去除头部会消耗 O(n) 的时间。if node:# 维护最大深度max_depth = max(max_depth, depth)# 由于每一层最后一个访问的节点才是答案，因此需要不断更新深度信息rightmost_value_at_depth[depth] = node.valqueue.append((node.left, depth+1))queue.append((node.right, depth+1))# 构造从上到下的右视图结果ans = []for depth in range(max_depth+1):ans.append(rightmost_value_at_depth[depth])return ans
2. 二叉树的层平均值
题目链接：二叉树的层平均值 - leetcode
题目描述：
给定一个非空二叉树的根节点root, 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
题目归纳：
层序遍历+求平均值
解题思路：
解法： 二叉树的层平均值 - leetcode官方题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:# 层序遍历if not root: return []queue = deque([root])ans = []Sum = 0while queue:lenq = len(queue)Sum = 0# 取出该层的节点，并计算平均值for i in range(lenq):node = queue.popleft()Sum += node.valif node.left: queue.append(node.left)if node.right: queue.append(node.right)ans.append(float(Sum / lenq))return ans
3. 二叉树的层序遍历
题目链接：二叉树的层序遍历 - leetcode
题目描述：
给你二叉树的根节点root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
题目归纳：
就是原始的层序遍历
解题思路：
解法： 二叉树的层序遍历 - leetcode官方题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root: return []ans = []queue = [root]# 传统的层序遍历写法：有2层循环while len(queue) > 0:# 当前层的节点个数curr_layer_len = len(queue)ans.append([])for i in range(curr_layer_len):node = queue.pop(0)ans[-1].append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)return ans
4. 二叉树的锯齿形层序遍历
题目链接：二叉树的锯齿形层序遍历 - leetcode
题目描述：
给你二叉树的根节点root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
题目归纳：
层序遍历不要动，取元素的队列来回折返即可。
解题思路：
解法： 二叉树的锯齿形层序遍历 - leetcode官方题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root: return []left_to_right = False # Flag变量. True表示从左往右遍历，False表示从右往左遍历ans = []queue = deque([root])while queue: # 遍历列表lenq = len(queue)layer = deque([]) # 取元素的双端队列，左右折返放置元素for i in range(lenq): # 遍历该层节点node = queue.popleft() # 队头if left_to_right: layer.appendleft(node.val) # 往双端队列的左边插入if node.left: queue.append(node.left) # 记得，一直都是先append(left)再append(right)if node.right: queue.append(node.right)else: # right_to_rightlayer.append(node.val) # 往双端队列的右边插入if node.left: queue.append(node.left)if node.right: queue.append(node.right)ans.append(list(layer)) # 双向链表deque转换成listleft_to_right = not left_to_rightreturn ans
这篇关于Leetcod面试经典150题刷题记录 —— 二叉树层次遍历篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
