104.二叉树的最大深度
本题很容易想到采用层次遍历的思路来解决，因为要求的是二叉树的最大深度，那么在进行层次遍历的时候设置一个变量count用来记录当前遍历的层数，count初始为0，每遍历完一层将其值+1，最后返回该值即为二叉树的最大深度。
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
count = 0
queue = deque([root])
# 与层次遍历的代码基本一致，只需要在每次for循环结束后将count+1即可
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
count += 1
return count559.n叉树的最大深度
思路与二叉树基本一致，仅需把左右孩子改为children即可。
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
count = 0
queue = deque([root])
while queue:
for _ in range(len(queue)):
node = queue.popleft()
for child in node.children: # 仅需修改此处
queue.append(child)
count += 1
return count111.二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。本题首先想到的就是采用层次遍历的做法，每遍历一层深度+1，当遇到第一个叶子结点（左右孩子都为空的结点）时，返回当前的深度即可。迭代法层序遍历的代码如下：
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root: # 若根结点为空则深度为0
return 0
queue = deque([root])
depth = 1 # 深度初始值为1
while queue: # 层次遍历
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not node.left and not node.right: # 若左右孩子都为空，则说明是叶子结点，直接返回当前深度
return depth
depth += 1 # 每次for循环结束相当于遍历完了一层，对深度+1如果考虑使用递归法，则需要使用前序或后序遍历。本题采用递归法后序遍历实现。求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
先求左子树深度，再求右子树深度，最后遍历中间根节点给高度加上1。体现了后序遍历的逻辑。
class Solution:
def getDepth(self, node):
if node is None:
return 0
leftDepth = self.getDepth(node.left) # 左子树最小深度
rightDepth = self.getDepth(node.right) # 右子树最小深度
# 当一个左子树为空，右不为空，这时并不是最低点
if node.left is None and node.right is not None:
return 1 + rightDepth
# 当一个右子树为空，左不为空，这时并不是最低点
if node.left is not None and node.right is None:
return 1 + leftDepth
result = 1 + min(leftDepth, rightDepth) # 左右都不为空，则返回左右子树中高度最小的一棵的深度+1
return result
def minDepth(self, root):
return self.getDepth(root)
222.完全二叉树的结点个数
本题同上面几题类似，采用层序遍历的思想来做很容易解决。仅需在遍历每一层是记录一下当前层的结点个数即可，最后返回所有层结点个数的总和。
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([root])
count = 0
while queue:
count += len(queue) # count加上当前层的结点个数
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count
但本题考查的是求完全二叉树的节点个数，所以可以利用完全二叉树的特性。在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
left = root.left
right = root.right
leftDepth = 0 # 这里初始为0是为了下面求指数方便
rightDepth = 0
while left: # 求左子树深度
left = left.left
leftDepth += 1
while right: # 求右子树深度
right = right.right
rightDepth += 1
if leftDepth == rightDepth:
return (2 << leftDepth) - 1 # 注意(2<<1) 相当于2^2，所以leftDepth初始为0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
