Python 刷题笔记：二叉树专题二
昨天接触了二叉树中的前中后三序遍历的代码实现，今天来看剩下的那种层序遍历。
题目一
「第 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 关于二叉树的题目（外加一道面试题目），明天二叉树先告一段落、继续换个专题练习。
腾讯云开发者
