汀的知识碎片

03 二叉树结构判定：相同树、对称树与平衡二叉树

7 min read

二叉树结构判定：相同树、对称树与平衡二叉树

摘要

二叉树里的判定题往往比遍历题更能暴露思维漏洞。LeetCode 100、101、110 分别代表三类典型任务：判断两棵树是否完全一致、判断一棵树是否镜像对称、判断一棵树是否高度平衡。它们都能用递归解决，但递归函数的定义各不相同。本文会用这三道题讲清楚：什么时候函数返回布尔值就够了，什么时候必须让函数同时携带“是否合法”和“高度”两类信息。

第 1 章 LeetCode 100：Same Tree

1.1 问题本质

相同树检查的是两件事：

  1. 对应位置的节点值是否相等
  2. 对应位置的结构是否完全一致

只比较值不够，因为 [1,2] 和 [1,null,2] 的遍历序列可能部分重合，但结构不同；只比较结构也不够，因为值可能不同。

1.2 递归写法

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (p.val != q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

这里函数语义非常直接：给我两棵树，我返回它们是否相同。

第 2 章 LeetCode 101：Symmetric Tree

2.1 为什么不能直接比较左右子树

很多人第一反应是：判断 root.left 和 root.right 是否相同。但对称不是“相同”，而是“互为镜像”：

  • 左子树的左孩子对应右子树的右孩子
  • 左子树的右孩子对应右子树的左孩子

这意味着比较关系发生了交叉。

2.2 递归函数要改成“镜像比较”

public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}
 
private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    if (left.val != right.val) {
        return false;
    }
    return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}

Same Tree 比较的是“平行位置”；Symmetric Tree 比较的是“镜像位置”。这就是两道题最大的区别。

2.3 迭代写法的思路

也可以用队列成对放入节点：

  • 每次同时取出两个节点
  • 比较它们是否镜像
  • 按 (left.left, right.right)、(left.right, right.left) 的顺序继续入队

这类成对比较的迭代题，本质上是在显式模拟递归参数对。

第 3 章 LeetCode 110：Balanced Binary Tree

3.1 为什么“先算高度再判平衡”会慢

最直观的思路是：

  1. 对每个节点分别求左子树高度、右子树高度
  2. 比较高度差是否超过 1
  3. 再递归判断左右子树是否平衡

这个写法是正确的，但会重复计算高度，最坏复杂度退化到 。

3.2 正确思路：后序遍历一次返回高度

因为“当前节点是否平衡”依赖左右子树高度，而高度必须先由子树给出，所以这是一个标准后序问题。

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
 
private int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
 
    int leftHeight = height(node.left);
    if (leftHeight == -1) {
        return -1;
    }
 
    int rightHeight = height(node.right);
    if (rightHeight == -1) {
        return -1;
    }
 
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
 
    return Math.max(leftHeight, rightHeight) + 1;
}

这里 -1 不是高度，而是一个“失败哨兵值”，表示这棵子树已经不平衡。这样可以把“判断平衡”和“返回高度”合并到一次递归中。

3.3 为什么这道题是树形 DP 的前奏

因为它已经体现了树题里最典型的模式：

  • 左子树先算出结果
  • 右子树再算出结果
  • 当前节点拿到左右结果后完成汇总
  • 汇总结果继续返回给父节点

这就是树形 DP 的基本骨架。后面的 二叉树中的最大路径和 只是把返回值和全局状态变复杂了。

第 4 章 三道题的递归语义对比

题目函数输入函数返回值本质
Same Tree两棵树是否相同平行比较
Symmetric Tree两棵镜像位置子树是否镜像交叉比较
Balanced Binary Tree一棵树高度或失败标记后序汇总

从这张表可以看出，树题真正决定难度的不是遍历方式，而是递归函数的语义设计。

先定义函数，再写代码

面试里如果你先把函数语义说清楚，代码几乎会自然长出来；如果一上来写 if (root == null)，通常意味着思路还没抽象稳定。

第 5 章 常见误区

5.1 把 Symmetric Tree 写成 Same Tree

这是最常见错误。原因不是不会递归，而是没有真正看到“镜像”这个关系变化。

5.2 在 Balanced Binary Tree 里重复算高度

只要一个节点每次都重新调用 maxDepth 求左右高度，就说明没有把“高度”作为子树返回值复用起来。

5.3 只关注值，不关注 null 结构

树题很多 bug 都不是值比较错了，而是 null 分支没有对齐。树结构问题里，null 本身就是一种信息。

下一篇预告

04 二叉树指针操作：展开链表与填充右侧指针 会把注意力从“判断”转向“改造”。一旦开始原地修改指针，递归的副作用和层序连接的控制边界都会更复杂，这也是二叉树题进入工程感的一步。

Backlinks