【LeetCode】102. Binary Tree Level Order Traversal 解题报告(Python)
2024-10-18 09:05:25
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目描述
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
题目大意
求二叉树的层次遍历。
解题方法
DFS
DFS方法还是很常见的,由于DFS的顺序并不是层次的顺序,所以我们需要一个变量depth表示当前遍历到了哪层了,把当前节点的值放入对应层的列表最后即可。
为什么需要if len(res) == level: res.append([])
呢?,这句话的意思其实是当我们循环到了一个新的层,那么就给它加一层。
Python代码如下,应该能背会。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
self.level(root, res, 0)
return res
def level(self, root, res, depth):
if not root: return
if depth >= len(res):
res.append([])
res[depth].append(root.val)
self.level(root.left, res, depth + 1)
self.level(root.right, res, depth + 1)
BFS
使用队列的方法。
学习了java队列的使用。在一个队列中,放入第一个元素,取出后,放入左右孩子,再根据左右孩子逐个放入其后相应的孩子。队列为空的时候,说明已经遍历完成。
这个方法非常好,学习了。
public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList result = new ArrayList();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> level = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode head = queue.poll();
level.add(head.val);
if (head.left != null) {
queue.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
result.add(level);
}
return result;
}
python版的用队列,deque直接append,然后popleft()就可以了。因为是双向链表,所以不要appendleft()和popleft()同时用,否则是栈。。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
if not root: return res
queue = collections.deque()
queue.append(root)
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
日期
2015/10/13 19:25:00 —— 一刷
2018 年 3 月 14 日 —— 二刷,霍金先生去世日
2019 年 3 月 24 日 —— 三刷,转眼又是一年
最新文章
- 8-07CONTIUE 、 BREAK、RETURN
- 【python】用setup安装自定义模块和包
- [OpenJudge0054]特务会议召开
- hadoop,hbase,pig安装
- Uva12504 Updating a Dictonary
- UVALive 4128 Steam Roller(最短路(拆点,多状态))
- KMeans聚类算法Hadoop实现
- 今天修改bug基本完成
- Swift - 使用NSURLSession加载数据、下载、上传文件
- ie8兼容background-size属性
- 字符编码知识简介和iconv函数的简单使用
- Android 使用shape定义不同控件的的颜色、背景色、边框色
- python爬虫requests的使用
- Spring Security 实战:QQ登录实现
- junit+mock+spring-test构建后台单元测试
- ajax基本原理与案例
- Siki的虚幻第一季
- Linux内存、性能诊断中vmstat命令的详解
- vb编程中的选择结构语句的写法
- Linux操作redis 使用(VMwareWorkstation)