题目来源：改编自 LeetCode 110. 平衡二叉树。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。
学习目标
前置知识与环境
先阅读第 8.3 节 平衡查找树的"旋转为何可行"与"AVL 的高度与复杂度"两节：平衡条件是旋转的依据，而"AVL 树高度为
本题的树不要求是二叉搜索树，只看形态；先在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。
任务
给定一棵以编号 0 为根的二叉树（共 n 个结点）。若树中每个结点都满足"左右子树高度差 ≤ 1"（空子树高度记为 0，叶结点高度记为 1），输出 1；只要有一个结点违反，输出 0。空树（n = 0）视为平衡，输出 1。
输入格式
- 第一行：一个整数
n，为结点数； - 接下来
n行：每行四个整数i val l r，表示编号为i的结点关键字为val，左孩子编号为l、右孩子编号为r，-1表示空；编号 0 是根，val可能很大，请用 64 位整数读入。
输出格式
一行一个整数：整棵树满足 AVL 平衡条件输出 1，否则输出 0。
数据范围与限制
| 项目 | 范围 |
|---|---|
结点数 n | 0 ≤ n ≤ 10⁴ |
| 结点编号 | 0 ≤ i < n，孩子编号为 −1 或 [0, n) 内的合法编号 |
关键字 val | −10¹⁸ < val < 10¹⁸（用 long long 读入，本题不使用其大小关系） |
| 时间复杂度要求 | 整体 |
正常、边界与错误情况
- 正常：满二叉树、完全二叉树输出
1；一侧偏长的"接近平衡"树只要每个结点高度差 ≤ 1 也输出1； - 边界：
n = 0（空树）与n = 1（单结点）都输出1；整条链（见用例 004）输出0； - 深层失衡：失衡可能只出现在很深的位置（见用例 005），从根往下看几层就下结论的写法会判错；
- 易混情形：所有叶子的深度范围不能代替逐结点高度差——存在"整体平衡但叶子深浅相差超过 1"的树（见用例 006），也存在"叶子深度只差 1 但中间结点失衡"的树。
样例
样例 1
7
0 42 1 2
1 7 3 4
2 99 5 6
3 3 -1 -1
4 15 -1 -1
5 64 -1 -1
6 128 -1 -11这是一棵深度为 3 的满二叉树：每个叶结点高度 1，7、99 的两个孩子都是叶子（差 0），根的左子树高 2、右子树高 2（差 0），全部满足条件，输出 1。
样例 2
3
0 100 1 -1
1 50 2 -1
2 20 -1 -10三个结点构成一条向左的链：结点 1 高 2、右子树为空（差 2 > 1），结点 0 的左子树高 3、右子树为空（差 3 > 1），输出 0。
实现提示
写一个返回"高度或失衡标记"的函数：对空子树返回 0；递归求出左右高度后，若任一侧已经是失衡标记，或两侧高度差超过 1，就向上传递失衡标记（例如返回 -1）；否则返回 max(左, 右) + 1。这样每个结点只被访问一次。
相反，"对每个结点单独调用一次求高度函数再比较"的正确性没有问题，但每个结点都要重扫它的整棵子树，总代价是
运行
make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-08/exercise/E-08-08-balanced-binary-tree-check需要单用例或严格评分时使用 make run CASE=005-deep-imbalance 与 make score；也可用 pnpm lab:score -- labs/chapter-08/exercise/E-08-08-balanced-binary-tree-check 兜底。
完成清单
思考与复盘
- 若把平衡条件写成"任意叶子深度差 ≤ 1"，用例 006 会在哪个结点上误判？画出该树的各结点高度。
- 本题判定的是"是否平衡"，而 AVL 树在失衡时还要旋转恢复。若要在失衡时输出"最接近失衡结点的旋转类型（LL/LR/RR/RL）"，你的函数需要额外返回什么信息？
- 递归深度最坏等于树高。当输入退化成 10⁴ 个结点的链时，你的实现递归多少层？如果担心栈溢出，如何改成显式栈的迭代后序？