从上到下打印二叉树
- 从上到下，广度优先（BFS），借助队列来实现
- 建立一个队列用于储存node信息，每次popleft；
- 建立一个列表用于打印，每次把node.value append进去
建立队列： collections.deque()
队列推入元素用： queue.append(x)
先进先出实现使用： queue.popleft()
而堆的实现方式可以直接使用 list + append() + pop() 实现
# 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[int]:
# 利用队列进行BFS
if not root:
return []
result = []
# 新建queue
queue = collections.deque()
# 初始化（把root node放进去）
queue.append(root)
while queue:
node = queue.popleft()
# 最左边的node pop出来（先进先出）
result.append(node.val)
# 把当前node的value放到result里 （打印输出）
#BFS，如果有左右子节点，把node放到queue里，再通过while打印输出
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
从上到下打印二叉树（按行打印）
3
/
9 20
/
15 7
输出：[ [3], [9,20], [15,7] ]
- 每次while执行时，先确认queue当前长度，确认本次循环打印次数
# 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 not root:
return []
queue = collections.deque()
queue.append(root)
res = []
while queue:
length = len(queue)
row = []
# 记录queue当前元素个数，确定循环次数
for i in range(length):
node = queue.popleft()
row.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(row)
return res
从上到下打印二叉树（按行打印，之字顺序）
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
代码同上，最后加一个遍历偶数层倒序
for i in range(len(res)):
if i % 2 == 1:
res[i] = res[i][::-1]
遍历时，row不是简单的列表而是deque，偶数层，使用appendleft()
- 注意因为res是普通列表， 不可以直接把queue结构append进去
- 需要先转成list，再加入， res.append(list(queue))
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = collections.deque()
queue.append(root)
res = []
while queue:
row = collections.deque()
# 记录queue当前元素个数，确定循环次数
for i in range(len(queue)):
node = queue.popleft()
# 确认如果是偶数层，使用左插入
if len(res)%2 == 1:
row.appendleft(node.val)
else:
row.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 注意数据结构
res.append(list(row))
return res
树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
image.png
- 对称递归，多次调用 isSubStructure来判断当前Aroot和Broot是否是子树关系；或是使用递归确认A左子树、右子树是否满足
- 另外需要构建函数recur来确认“子树一致”；
** 停止条件为：B空了，匹配完了，True
** A空了，或A B值不同，False
** 递归：继续看AB的左子树是否一致；右子树是否一致
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def recur(A,B):
# B空了，即为匹配完了
if not B:
return True
# A空了，没匹配完，匹配不上了；
if not A:
return False
# A B节点值不同，匹配不上了
if A.val != B.val:
return False
# 如果当前节点匹配上了，继续比较左子树和右子树
return (recur(A.left,B.left) and recur(A.right,B.right))
# 特殊处理，两个树任意为空，返回false
if not (A and B):
return False
else:
# 返回A找B；或 A左子树找B；或 A右子树找B
return (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))
二叉树镜像
- 镜像递归，左边子树镜像完复制到右边；右边子树镜像完复制到左边
- 特殊情况/停止case：root节点为空，不需要镜像了，直接返回root
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root:
return root
# 镜像递归，左叶复制到右叶...
temp_left = self.mirrorTree(root.left)
temp_right = self.mirrorTree(root.right)
root.left = temp_right
root.right = temp_left
return root
对称二叉树判断
- 轴对称确认的点：相同的值为 左的左 和 右的右； 以及 左的右和右的左
- 因此递归确认是否对称的时候，需要确认 L.left, R.right 和 L.right, R.left
- 停止条件为同时越过叶子节点(node == None) --> True
- 返回False： 某一边None，或值不同
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
# 镜像递归，左的左 和 右的右 进行比较
def recur(L, R):
# 停止条件，都越过叶子节点了，True
if not L and not R: return True
# 如果值不想等，或只有一个为null，False
if not L or not R or L.val != R.val: return False
# 递归 【左的左】 和 【右的右】
return recur(L.left, R.right) and recur(L.right, R.left)
return recur(root.left, root.right)
