代码随想录算法训练营第十六天| 104. 二叉树的最大深度、111. 二叉树的最小深度、222. 完全二叉树的节点个数

代码随想录算法训练营第十六天| 104. 二叉树的最大深度、111. 二叉树的最小深度、222. 完全二叉树的节点个数

题目

104.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0q_ = deque()q_.append(root)sum_ = 0while q_:sum_ += 1level_ = []for _ in range(len(q_)):node = q_.popleft()level_.append(node)if node.left:q_.append(node.left)if node.right:q_.append(node.right)return sum_

题目

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:def minDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0q_ = deque()q_.append(root)dept_ = 0while q_:dept_ += 1level_ = []for _ in range(len(q_)):node = q_.popleft()if node.left:q_.append(node.left)if node.right:q_.append(node.right)if not node.left and not node.right:return dept_return dept_

题目

222.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:# 递归# if not root:#     return 0# return self.countNodes(root.left) + self.countNodes(root.right) + 1# 非递归if not root:return 0;res = 0q_ = deque()q_.append(root)while q_:for _ in range(len(q_)):node = q_.popleft()res += 1if node.left:q_.append(node.left)if node.right:q_.append(node.right)return res