二叉树的属性：深度、平衡、对称与路径

高度 vs 深度：一张表分清

这两个词天天混用，但在解题时差别实打实影响遍历顺序的选择：

概念	度量对象	方向	对应遍历	递归返回含义
深度 depth	从根到该节点路径长	自顶向下	前序（信息随根下行）	当前节点离根多远
高度 height	从该节点到最远叶子	自底向上	后序（信息从孩子上交）	当前节点离叶多远

记忆口径：求深度用前序"往下传"，求高度用后序"往上传"。

前序求深度：把当前深度作为参数往下带，depth(root.left, depth + 1)——父节点的信息先于孩子存在；
后序求高度：先递归左右拿到两个子树的高度，再 max(l, r) + 1——孩子算完父母才能拍板。

理解了这一点，"求深度也可以用后序写"（max(l,r)+1 算出的其实是整树最大深度）就不再矛盾：整棵树的最大深度 = 根的高度，同一个值可以由两种方向得到，只是函数含义和写法不同。

最大深度（104）与最小深度（111）

104 最大深度是后序高度写法的标准示范：

public int maxDepth(TreeNode root) {
    if (root == null) return 0;          // 空节点高度 0，递归出口
    int l = maxDepth(root.left);         // 左子树最大高度
    int r = maxDepth(root.right);        // 右子树最大高度
    return Math.max(l, r) + 1;           // 自己站在更高的一边上面
}

111 最小深度定义为"根到最近叶子的最短路径长度"，直接把 104 的 max 换成 min 是错的——会踩"单侧为空"的坑：

        1
         \
          2
按 min(l,r)+1 算：min(0, 2) + 1 = 1   ✗
正确答案：根到叶子 2 的路径，长度 2    ✓

问题出在节点 1 没有左孩子：空子树根本不通向任何叶子，不能参与 min 竞争。只有"左右孩子都存在"时才能放心取 min；单侧为空时必须走另一侧：

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null) return minDepth(root.right) + 1; // 左空：只能向右
    if (root.right == null) return minDepth(root.left) + 1; // 右空：只能向左
    // 两边都有孩子，才能取两侧较小者
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

这题的价值不在代码量，而在提醒：树题里"孩子缺失"永远是一等公民，凡是涉及"到叶子"的路径问题，都要先问自己"另一边是空的时候怎么办"。

对称二叉树（101）：内外双指针递归

判断左右子树是否镜像对称，不能各自遍历自己——镜像比较必须成对进行。递归函数干脆接收两个节点，一对一对地比：

外侧对：左子树的左孩子 vs 右子树的右孩子；
内侧对：左子树的右孩子 vs 右子树的左孩子。

          1                外侧：2L ↔ 2R'   （图中 1↔3 的位置）
        /   \
      2       2'            内侧：2R ↔ 2L'
     / \     / \
    3   4   4'  3'

public boolean isSymmetric(TreeNode root) {
    return compare(root.left, root.right);
}
 
// compare(a, b)：a 和 b 所在的"镜像位"是否完全相同
private boolean compare(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;   // 两个都空：对称
    if (a == null || b == null) return false;  // 只有一个空：不对称
    if (a.val != b.val) return false;          // 值不同：不对称
    // 外侧对外侧比，内侧对内侧比
    return compare(a.left, b.right) && compare(a.right, b.left);
}

递归出口三连判的顺序有讲究：先"全空"、再"单空"、最后比值，任何一步短路都能避免空指针。这道题的函数签名值得记住——当单个节点携带的信息不够判断时，让递归函数同时接收"相关联的多个节点"，后序公共祖先（236）会把这个技巧再推进一步。

平衡二叉树（110）：返回 -1 剪枝

判断每个节点的左右子树高度差是否 ≤ 1。朴素写法是"先写个求高度的函数，再对每个节点调用一次"，复杂度 O(n²)——大量重复计算。

优化成 O(n) 只需要改造 104 的求高度函数：一旦发现不平衡，返回 -1 当作"错误信号"向上传播，上层看到 -1 直接继续上抛，不再做任何计算：

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
 
// 返回以 node 为根的子树高度；若子树不平衡，返回 -1
private int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left);
    if (l == -1) return -1;              // 左边已经塌了，不再深入
    int r = height(node.right);
    if (r == -1) return -1;              // 右边塌了同理
    if (Math.abs(l - r) > 1) return -1;  // 自己这里塌了
    return Math.max(l, r) + 1;           // 正常情况返回高度
}

这个技巧可以提炼成一句心法：让返回值兼职"错误信号"，负值一路穿透，剪掉所有无谓的递归。写"判断类 + 依赖子树信息"的题目时，先想想能不能设计一个"既表达结果又表达失败"的返回值。

路径总和（112）

题目：是否存在"根到叶子"路径，节点值之和恰好等于 target。技巧是让 target 沿途递减：访问节点时用 target - node.val 传下去，走到叶子时只需检查 target 是否恰好被减到 0：

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;          // 空节点：没有路径
    // 叶子节点：检查该路径的和是否恰好凑齐
    if (root.left == null && root.right == null) {
        return targetSum == root.val;
    }
    int rest = targetSum - root.val;         // 自己消耗一份
    return hasPathSum(root.left, rest)       // 左边有路即可
        || hasPathSum(root.right, rest);     // 右边有路即可
}

两个易错点：其一，"路径"必须是根到叶子，单侧为空的节点不是叶子（呼应 111 的坑）；其二，|| 的短路特性天然完成了"找到一条就停"的剪枝。衍生题 113（路径总和 II）收集所有路径，把返回 boolean 改为"带上路径列表 + 回溯撤销"即可。

递归返回值设计心得

本篇五道题，难度都不在"遍历"，而在给递归函数定协议。写题前先回答三个问题，答案落纸再动手：

问题	决策	例子
这个函数求什么？	返回值含义一句话说清	110：子树高度（-1 表示不平衡）
需要从孩子收集什么？	后序"往上传"	104：左右高度取 max
需要传给孩子什么？	前序"往下传"	112：剩余目标值

再补三条实战经验：

返回 boolean 表示"存在性"，返回 int 表示"度量值"，负值可以兼职错误信号（110 的 -1）；
单节点信息不够就多传一个节点（101 的双指针递归）；
空节点永远是最先写的出口，其次才是"叶子/缺失孩子"特判（111 的单侧为空）。

养成"先定协议、再写单层逻辑"的习惯，二叉树题的正确率会明显上一个台阶。

LeetCode 题单

题号	题名	一句话考点
104	二叉树的最大深度	后序 max(l,r)+1，或前序带深度参数
111	二叉树的最小深度	单侧为空必须走另一侧，不能直接 min
110	平衡二叉树	高度函数返回 -1 当错误信号，O(n) 剪枝
101	对称二叉树	双节点镜像递归，外侧对 vs 内侧对
112	路径总和	target 递减，叶子判断 ==
113	路径总和 II	收集所有路径 + 回溯撤销
100	相同的树	双节点递归的简化版
222	完全二叉树的节点个数	普通计数 O(n)；利用满二叉树性质可 O(log²n)

参考

代码随想录 · 二叉树专题