38 二叉树的深度

题目描述

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

核心思想：递归。树的深度 = max(左子树深度, 右子树深度) + 1。

时间复杂度：O(n) 空间复杂度：O(n)（递归栈）

Python 实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 递归版本
def tree_depth(root):
    """
    求二叉树的深度（递归）
    """
    if not root:
        return 0

    left_depth = tree_depth(root.left)
    right_depth = tree_depth(root.right)

    return max(left_depth, right_depth) + 1


# 迭代版本（层序遍历）
def tree_depth_iterative(root):
    """
    求二叉树的深度（迭代，层序遍历）
    """
    if not root:
        return 0

    from collections import deque
    queue = deque([root])
    depth = 0

    while queue:
        depth += 1
        # 遍历当前层的所有节点
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth


# 测试代码
if __name__ == "__main__":
    # 创建树:
    #     1
    #    / \
    #   2   3
    #  / \
    # 4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    print(f"树的深度（递归）: {tree_depth(root)}")
    print(f"树的深度（迭代）: {tree_depth_iterative(root)}")

# 输出:
# 树的深度（递归）: 3
# 树的深度（迭代）: 3

图解

示例树:
        1
       / \
      2   3
     / \
    4   5

递归计算:
depth(1) = max(depth(2), depth(3)) + 1
         = max(2, 1) + 1
         = 3

depth(2) = max(depth(4), depth(5)) + 1
         = max(1, 1) + 1
         = 2

depth(3) = max(depth(None), depth(None)) + 1
         = max(0, 0) + 1
         = 1

depth(4) = max(0, 0) + 1 = 1
depth(5) = max(0, 0) + 1 = 1

最终深度: 3