【深基16.例3】二叉树深度

题意

给出最多一百万节点二叉树的左右儿子编号，根为 1，求最大层数。

思路

递归公式是 depth(node)=1+max(depth(left),depth(right))，但极端链形树会超过 Python 递归深度。

使用显式栈保存待访问节点和它的层数。每弹出一个节点就更新最大值，并把非空孩子以 depth+1 入栈。

Python 知识

array('i') 以紧凑 C 整数保存百万编号，避免普通 Python 整数列表的较大对象开销。
两个 array 分别保存节点和深度，最坏链形树也不会递归爆栈。
pop/append 把数组当后进先出栈。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：Python 递归深度限制。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：显式状态遍历。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30import sys
from array import array


input = sys.stdin.buffer.readline
n = int(input())
left = array("i", [0])
right = array("i", [0])

for _ in range(n):
    left_child, right_child = map(int, input().split())
    left.append(left_child)
    right.append(right_child)

nodes = array("i", [1])
depths = array("i", [1])
maximum_depth = 0

while nodes:
    node = nodes.pop()
    depth = depths.pop()
    maximum_depth = max(maximum_depth, depth)
    if left[node]:
        nodes.append(left[node])
        depths.append(depth + 1)
    if right[node]:
        nodes.append(right[node])
        depths.append(depth + 1)

print(maximum_depth)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * P4913 【深基16.例3】二叉树深度
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

// 结点结构：左孩子、右孩子编号（0 表示无）
struct Node {
    int l, r;
} tree[MAXN];
int n;

// DFS 求深度
int dfs(int u) {
    if (u == 0) return 0;
    return max(dfs(tree[u].l), dfs(tree[u].r)) + 1;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &tree[i].l, &tree[i].r);
    }
    printf("%d\n", dfs(1));
    return 0;
}

复杂度

每个节点访问一次，时间复杂度 $O(n)$ ；左右儿子和显式栈空间为 $O(n)$ 。

总结

百万节点时，算法仍是普通 DFS，但 Python 实现必须同时关注递归深度和整数对象内存，array 加显式栈更稳。

【深基16.例3】二叉树深度

目录

题意

思路

Python 知识

代码

复杂度

总结