104. 二叉树的最大深度 - 力扣（LeetCode）

image.png

解题思路

前序遍历和后续遍历都可以，注意区分高度和深度

# 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 not root:
            return 0

        deep_left = self.maxDepth(root.left)
        deep_right = self.maxDepth(root.right)

        deep = 1 + max(deep_left, deep_right)

        return deep

111. 二叉树的最小深度 - 力扣（LeetCode）

image.png

解题思路

和求最大深度差不多，注意叶子节点不是空

# 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 not root :
            return 0

        deep_left = self.minDepth(root.left)
        deep_right = self.minDepth(root.right)

        if root.left == None and root.right != None:
            return 1 + deep_right
        elif root.left != None and root.right == None:
            return 1 + deep_left

        return  1 + min(deep_left,deep_right)

222. 完全二叉树的节点个数 - 力扣（LeetCode）

解题思路

普通二叉树：层序遍历和后序递归；完全二叉树：如果是满二叉树就可以直接利用公式计算节点个数，假如完全二叉树的左右深度都一样就是满二叉树。

# 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 not root:
            return 0

        c_left = self.countNodes(root.left)
        c_right = self.countNodes(root.right)
        return  1 + c_left + c_right

# 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 not root:
            return 0

        count = 0
        queue = collections.deque([root])

        while queue:
            n = len(queue)

            for _ in range(n):
                cur  = queue.popleft()
                count += 1

                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)

        return count

# 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

# 完全二叉树方法 满二叉树节点个数：2^depth-1
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left = root.left
        right = root.right
        left_depth = 1
        right_depth = 1 #方便后续进行位运算，写0

        while left: #计算左边的深度
            left = left.left
            left_depth += 1

        while right: # 计算右边的深度
            right = right.right
            right_depth += 1

        if left_depth == right_depth: #满二叉树
           return (2 ** left_depth) - 1 

        left_count = self.countNodes(root.left)
        right_count = self.countNodes(root.right)

        count = left_count + right_count +1 

        return count