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

今日任务：

LeetCode104 二叉树的最大深度
LeetCode111 二叉树的最小深度
LeetCode222 完全二叉树的节点个数

资料来源：

1 LeetCode104 二叉树的最大深度

题目

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

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

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：


输入：root = [1,null,2]
输出：2

提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

迭代层序秒了。递归前序/后序也能做，不过注意得有回溯的过程。

python
# 二叉树
from collections import deque
from typing import Optional

# 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
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        queue = deque()
        depth = 0
        node = root
        queue.append(node)
        while len(queue) != 0:
            size = len(queue)
            if size != 0:
                depth += 1
            for _ in range(size):
                node = queue.popleft()
                if node.right is not None:
                    queue.append(node.right)
                if node.left is not None:
                    queue.append(node.left)
        return depth

python
# n叉树
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
from collections import deque


class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0
        queue = deque()
        node = root
        depth = 0
        queue.append(node)
        while len(queue) != 0:
            size = len(queue)
            if size != 0:
                depth += 1
            for _ in range(size):
                node = queue.popleft()
                if node is not None:
                    for i in node.children:
                        queue.append(i)
        return depth

2 LeetCode111 二叉树的最小深度

题目

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

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

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

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：


输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

迭代层序一样秒了。前序/后序一样能做，前序要注意回溯，后序要注意的是返回值是高度，遇到左子树和右子树中只有一个为空的时候，高度要取那个不为空的子树的高度+1，不能直接对这俩取最小值。

python
from collections import deque
from typing import Optional

# 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
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        node = root
        queue = deque()
        min_depth = 0
        queue.append(node)
        while len(queue) != 0:
            size = len(queue)
            min_depth += 1
            for _ in range(size):
                node = queue.popleft()
                if node.right is None and node.left is None:
                    return min_depth
                else:
                    if node.right is not None:
                        queue.append(node.right)
                    if node.left is not None:
                        queue.append(node.left)

3 LeetCode222 完全二叉树的节点个数

题目

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

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

示例 1：


输入：root = [1,2,3,4,5,6]
输出：6

示例 2：


输入：root = []
输出：0

示例 3：


输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

简单一点的，就是按照随便一种二叉树遍历方式，把整个二叉树都遍历一次。如果是进阶要求的话，可以利用完全二叉树的特性进行计算。

完全二叉树无非两种情况：要么最后一层是满的，要么最后一层没满。如果满了，那么就能使用公式 $2 ^ {树深度} - 1$ 来计算。重点来了，如果没满，可以将其分解为满的完全二叉树和没满的完全二叉树，再分别进行计算。

如何判断一棵树是不是完全二叉树呢？分别从左节点和右节点出发，一路向左/右，如果不是同时到达叶子节点，这棵树就不是满的完全二叉树。

按照这个思路，就有了以下代码。

python
from typing import Optional

# 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
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return self.countNodes_recursion(root)

    def countNodes_recursion(self, root: TreeNode) -> int:
        left_count = 0
        if root.left is not None:
            if self.is_complete(root.left):  # 判断左子树是不是满二叉树
                left_count = self.count_complete_tree(root.left)  # 是的话直接调公式
            else:
                left_count = self.countNodes_recursion(root.left)  # 不是的话再递归分解
        right_count = 0
        if root.right is not None:  # 同上
            if self.is_complete(root.right):
                right_count = self.count_complete_tree(root.right)
            else:
                right_count = self.countNodes_recursion(root.right)
        return 1 + left_count + right_count

    def count_complete_tree(self, root: TreeNode) -> int:
        pointer = root
        left_depth = 0
        while pointer is not None:  # 计算深度
            left_depth += 1
            pointer = pointer.left
        return 2 ** left_depth - 1  # 公式

    def is_complete(self, root: TreeNode) -> bool:  # 判断是不是满二叉树
        pointer = root
        left_depth = 0
        right_depth = 0
        while pointer is not None:
            left_depth += 1
            pointer = pointer.left
        pointer = root
        while pointer is not None:
            right_depth += 1
            pointer = pointer.right
        return left_depth == right_depth

目录

1 LeetCode104 二叉树的最大深度

2 LeetCode111 二叉树的最小深度

3 LeetCode222 完全二叉树的节点个数