2023-12-14 二叉树的最大深度和二叉树的最小深度以及完全二叉树的节点个数

二叉树的最大深度和二叉树的最小深度以及完全二叉树的节点个数

104. 二叉树的最大深度

思想：可以使用迭代法或者递归！使用递归更好，帮助理解递归思路！明确递归三部曲–①确定参数以及返回参数 ②递归结束条件 ③单层逻辑是怎么样的！

# 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:
        # 确定递归的参数以及返回
        # 什么时候结束递归
        # 递归的单层逻辑是怎么样的
        def dp(node):
            if not node:
                return 0
            left_length = dp(node.left)
            right_length = dp(node.right)

            return 1 + max(left_length, right_length)
        return dp(root)

111. 二叉树的最小深度

思想：看似和最大深度相似，实则不同的！还需要考虑一个节点为None但是另一个不为None的情况！这个是关键！如果是参加面试最好使用迭代法来做，也就是广度优先遍历这样会更快更好理解【判断节点是否有左右节点即可】

# 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:
        # 使用递归的方法--参数为TreeNode 返回int；结束条件左右节点皆为None；单层逻辑；
        def deth_dp(node):
            if not node:
                return 0
            left_length = deth_dp(node.left)
            right_length = deth_dp(node.right)
            # 还需要判断目前是否已经是叶子节点了
            if not node.left and node.right:
                return 1 + right_length
            elif node.left and not node.right:
                return 1 + left_length
            # 最后都为None 直接比较返回就好了
            return 1 + min(left_length, right_length)
        return deth_dp(root)

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

思想：和最大深度很像，返回值等于左右节点相加即可！

# 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:
        def add_deth(node):
            if not node:
                return 0
            left_length = add_deth(node.left)
            right_length = add_deth(node.right)
            return 1 + left_length + right_length
        return add_deth(root)