104.二叉树的最大深度

最大深度是3

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 主方法，用于启动深度计算过程
        return self.getDepth(root)
        
    def getDepth(self, node):
        # 递归方法，用于计算节点的深度
        if not node:
            # 如果当前节点为空，说明到达了叶子节点的下一个位置，返回深度0
            return 0
        leftheight = self.getDepth(node.left) # 对左子树递归调用getDepth，计算左子树的深度
        rightheight = self.getDepth(node.right) # 对右子树递归调用getDepth，计算右子树的深度
        # 当前节点的深度是左右子树深度的最大值加1（加的这1代表当前节点的深度贡献）
        height = 1 + max(leftheight, rightheight)
        return height

111.二叉树的最小深度

可能存在只有一边有节点的情况

class Solution:
    def getDepth(self, node):
        if node is None:
            return 0
        leftDepth = self.getDepth(node.left)  # 左
        rightDepth = self.getDepth(node.right)  # 右
        
        # 当一个左子树为空，右不为空，这时并不是最低点
        if node.left is None and node.right is not None:
            return 1 + rightDepth
        
        # 当一个右子树为空，左不为空，这时并不是最低点
        if node.left is not None and node.right is None:
            return 1 + leftDepth
        
        result = 1 + min(leftDepth, rightDepth)
        return result

    def minDepth(self, root):
        return self.getDepth(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: TreeNode) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 0 #这里初始为0是有目的的，为了下面求指数方便
        rightDepth = 0
        while left: #求左子树深度
            left = left.left
            leftDepth += 1
        while right: #求右子树深度
            right = right.right
            rightDepth += 1
        if leftDepth == rightDepth:
            return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth初始为0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1