代码随想录算法训练营Day 14|104.二叉树的最大深度,559.n叉树的最大深度,111.二叉树的最小深度,222.完全二叉树的节点个数

题目简介

104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

559.n叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

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

初见思路

递归法，很直观；如果想要用迭代法解，可以考虑用层序遍历。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1

层序每层递归寻找子节点最大的深度即可。层序遍历递归比较类似，闲着可以写一下。

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0

        depth = 0
        for i in range(len(root.children)):
            depth = max(depth, self.maxDepth(root.children[i]))
        
        return depth + 1

迭代法即可，有一个坑是要考虑根节点一边为空的极端情况。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        # 极端情况
        if (not root.left) and root.right:
            return self.minDepth(root.right) + 1
        if root.left and (not root.right):
            return self.minDepth(root.left) + 1

        return min(self.minDepth(root.left),self.minDepth(root.right)) + 1

直接层序遍历

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = collections.deque([root])

        node_cnt = 0
        while queue:
            size = len(queue)
            node_cnt += size

            for _ in range(size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return node_cnt