一、层次遍历

二、训练

2.1、637. 二叉树的层平均值

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def averageOfLevels(self, root: TreeNode) -> List[float]: if not root: return [] ret = [] que = [root] while que: queSize = len(que) cSum = 0 for i in range(queSize): node = que.pop(0) cSum += node.val if node.left: que.append(node.left) if node.right: que.append(node.right) ret.append(cSum/queSize) return ret

2.2、107. 二叉树的层次遍历 II

class Solution: def levelOrderBottom(self, root: TreeNode) -> List[List[int]]: que = [] que.append(root) ret = [] while len(que) > 0: queSize = len(que) subList = [] for i in range(queSize): cur = que.pop(0) if cur: subList.append(cur.val) que.append(cur.left) que.append(cur.right) if len(subList) > 0: ret.append(subList) ret.reverse() return ret

2.3、102. 二叉树的层次遍历

class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] que = [root] ret = [[root.val]] while que: queSize = len(que) curRet = [] for i in range(queSize): node = que.pop(0) if node.left: que.append(node.left) curRet.append(node.left.val) if node.right: que.append(node.right) curRet.append(node.right.val) if curRet: ret.append(curRet) return ret

2.4、111. 二叉树的最小深度

class Solution: def minDepth(self, root: TreeNode) -> int: if not root: return 0 que = [] que.append(root) level = 0 while len(que) > 0: queSize = len(que) for i in range(queSize): node = que.pop(0) if not node.left and not node.right: return level + 1 if node.left: que.append(node.left) if node.right: que.append(node.right) level += 1 return level

2.5、429. N叉树的层序遍历

class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: if not root: return [] ret = [[root.val]] que = [root] while que: queSize = len(que) curList = [] for i in range(queSize): node = que.pop(0) for n in node.children: if n: curList.append(n.val) que.append(n) if curList: ret.append(curList) return ret

2.6、993. 二叉树的堂兄弟节点

class Solution: def isCousins(self, root: TreeNode, x: int, y: int) -> bool: if not root: return False que = [root] while que: px = -1 py = -1 queSize = len(que) for i in range(queSize): node = que.pop(0) if node.left: que.append(node.left) if node.left.val == x : px = node.val if node.left.val == y: py = node.val if node.right: que.append(node.right) if node.right.val == x : px = node.val if node.right.val == y: py = node.val if px != -1 and py != -1 and px != py: return True return False

2.7、103. 二叉树的锯齿形层次遍历

相当于层次遍历，添加一个翻转标志

class Solution: def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] que = [root] ret = [[root.val]] rflag = False while que: queSize = len(que) curRet = [] for i in range(queSize): node = que.pop(0) if node.left: que.append(node.left) curRet.append(node.left.val) if node.right: que.append(node.right) curRet.append(node.right.val) if curRet: if rflag: ret.append(curRet) else: ret.append(curRet[::-1]) rflag = ~rflag return ret