昨天接触了二叉树中的前中后三序遍历的代码实现,今天来看剩下的那种层序遍历。
「第 102 题:二叉树的层序遍历」
难度:中等
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。
「示例:」
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
看其输出格式,是将二叉树每层的节点放到单独的列表中,而代码输入的是 root 根节点,要通过 root.left 取左子节点、root.right 取其右节点。那么可以每次都提取同一层的节点记录在同一列表中,遍历列表、取列表中节点的子节点,继续将结果放入同一列表中,直到最后一层。
# 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 root!=None:
level = [root]
# 若根节点空,保持列表为空,最终直接返回
else:
level = []
# 用来记录结果的列表
result = []
# 当层列表非空时
while level:
# 将层列表中的节点值组成列表存入结果中
result.append([ item.val for item in level if item!=None])
# 新的层列表
new_level = []
# 遍历当前层列表
for node in level:
# 如果左子节点非空
if node.left!=None:
# 将左子节点加入到新的层列表中
new_level.append(node.left)
# 同理处理右子节点
if node.right!=None:
new_level.append(node.right)
# 将新的子节点赋给层列表,带入下次循环
level = new_level
# 返回结果列表
return result
提交测试表现:
执行用时 : 48 ms, 在所有 Python3 提交中击败了 37.30% 的用户
内存消耗 : 14.1 MB, 在所有 Python3 提交中击败了 7.14% 的用户
原本想参考题解优化的,后来发现题解中提到的“广度优先搜索”方法下的代码逻辑与我们的代码基本相同。
❝广度优先搜索算法(英语:Breadth-First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 维基百科-广度优先搜索 ❞
挺开心的,可以独立做出二叉树的题了!
「面试题 检查平衡性」
难度:简单
实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过 1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/check-balance-lcci
这虽然标着个简单题,考虑半天没有头绪,想着如果通过层序遍历这二叉树,给每层节点记录高度,但越想就越复杂了。学习下题解里的优秀解法吧!
这里直接贴代码来学习:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 这里相当于定义了个全局变量
def __init__(self):
self.flag = True
def isBalanced(self, root: TreeNode) -> bool:
# 定义获取节点高度的函数,之后递归调用
def isb(root):
# 空节点,返回高度 0
if not root:
return 0
# 由左子树可计算出的高度=左子树高度+1
l = isb(root.left) + 1
# 由右子树计算的高度 = 右子树高度+1
r = isb(root.right) + 1
# 若左右子树高度差大于1
if abs(l-r)>1:
# 将全局的平衡状态改为 False
self.flag = False
# 返回左右计算的最大高度
return max(l,r)
# 由根节点开始执行函数
isb(root)
# 返回最终的平衡状态
return self.flag
#作者:skyyou-dang
#链接:https://leetcode-cn.com/problems/check-balance-lcci/solution/she-zhi-yi-ge-bian-liang-bao-cun-xia-mou-ge-jie-di/
原以为会是比较简单直接的计算高度方法,没想到用到了递归,以及通过 __init__ 中定义初始属性实现了全局变量的作用。我尝试着去掉这个 __init__ 中对 flag 的定义与使用,换成函数内的变量会麻烦很多。对类、方法、属性这些通过题目也有比较多接触,之后也要专门系统整理下相关内容。
这个解法思路,赞,多消化消化。
「第 226 题:翻转二叉树」
难度:简单
翻转一棵二叉树。
示例 1:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
示例 2:
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/invert-binary-tree
「解法一:」
看到这题,首先想到的还是遍历每个节点,然后将其左右子节点对调就可以了。遍历的过程还是用我们第一题里设计的层级遍历,应该就能一遍过。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
# 空节点单独处理下
if root ==None:
return None
# 层列表
level = [root]
# 层列表不为空,循环
while level:
# 装子节点的新列表
new_level = []
# 遍历层列表中的节点
for item in level:
# 对调左右子节点位置
item.left,item.right = item.right,item.left
# 若左子节点非空
if item.left:
# 加入到新列表中
new_level.append(item.left)
# 新列表添加非空右子节点
if item.right:
new_level.append(item.right)
# 层列表更新为新记录的子节点列表,进入下一层循环
level = new_level
# 对调完所有的,返回根节点
return root
提交测试表现:
执行用时 : 36 ms, 在所有 Python3 提交中击败了 80.20% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 5.26% 的用户
「解法二」
难得发现一道可以自己壮着胆子用递归的题目,既然是要翻转二叉树,那么翻转子树完全可以通过递归调用自身来实现,翻转完两子树,再将两子节点翻转即可!
代码一气呵成:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
# 空节点返回 None
if root==None:
return None
# 递归翻转左子树
self.invertTree(root.left)
# 递归翻转右子树
self.invertTree(root.right)
# 交换左右子节点
root.left, root.right = root.right,root.left
# 返回根节点
return root
提交测试表现:
执行用时 : 40 ms, 在所有 Python3 提交中击败了 61.62% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 5.26% 的用户
今天遇到的二叉树题目,要么是基于层序遍历,要么是基于递归实现,做起来也有豁然开朗的感觉。
二叉树初接触可能会不知所云,慢慢摸索规律还是挺有意思的。加上昨天,我们练习了五道 LeetCode 关于二叉树的题目(外加一道面试题目),明天二叉树先告一段落、继续换个专题练习。