代码随想录算法训练营第十六天| 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 0
        q_ = deque()
        q_.append(root)
        sum_ = 0
        while q_:
            sum_ += 1
            level_ = []
            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 0
        q_ = deque()
        q_.append(root)
        dept_ = 0
        while q_:
            dept_ += 1
            level_ = []
            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 = 0
        q_ = deque()
        q_.append(root)
        while q_:
            for _ in range(len(q_)):
                node = q_.popleft()
                res += 1
                if node.left:
                    q_.append(node.left)
                if node.right:
                    q_.append(node.right)
        return res