PHP实现对称二叉树判定：从思路设计到代码实现

2025年12月16日 互联网

一、对称二叉树的定义与判定核心

对称二叉树是指以根节点为对称中心，左右子树互为镜像的二叉树结构。其核心判定条件为：对于任意节点，其左子树的左子树与右子树的右子树对称，且左子树的右子树与右子树的左子树对称。这一特性决定了递归或迭代过程中需同时比较左右子树的对应节点。

以二叉树节点结构为例，每个节点包含val（值）、left（左子节点）、right（右子节点）三个属性。判定对称性时，需确保：

  1. 根节点为空时，直接返回true（空树视为对称）；
  2. 非空根节点下，左右子节点值相等；
  3. 左子树的左子树与右子树的右子树对称；
  4. 左子树的右子树与右子树的左子树对称。

二、递归实现：分治思想的典型应用

递归是解决对称二叉树问题的自然思路，通过分解问题为子问题，逐层比较对应节点。

1. 递归函数设计

定义辅助函数isMirror($left, $right)，参数为左右子树的根节点，返回布尔值表示是否对称。递归终止条件为：

  • 两个节点均为空：返回true；
  • 仅一个节点为空：返回false；
  • 节点值不等：返回false。

若终止条件未触发，则递归比较：

  • $left->left与$right->right；
  • $left->right与$right->left。

2. 主函数实现

主函数isSymmetric($root)处理根节点为空的情况，并调用isMirror比较左右子树：

  1. class TreeNode {
  2.     public $val;
  3.     public $left;
  4.     public $right;
  5.     function __construct($val = 0, $left = null, $right = null) {
  6.         $this->val = $val;
  7.         $this->left = $left;
  8.         $this->right = $right;
  9.     }
  10. }
  12. function isSymmetric($root) {
  13.     if ($root === null) return true;
  14.     return isMirror($root->left, $root->right);
  15. }
  17. function isMirror($left, $right) {
  18.     if ($left === null && $right === null) return true;
  19.     if ($left === null || $right === null) return false;
  20.     return ($left->val == $right->val) 
  21.         && isMirror($left->left, $right->right) 
  22.         && isMirror($left->right, $right->left);
  23. }

3. 递归的优缺点

  • 优点：代码简洁，逻辑清晰，直接映射问题定义。
  • 缺点：递归深度过大时可能导致栈溢出（PHP默认栈深度约100-200层），且重复计算较多。

三、非递归实现：迭代优化与队列应用

非递归方案通过迭代遍历节点，避免递归的栈开销，适合深度较大的二叉树。

1. 迭代思路

使用队列存储待比较的节点对，每次从队列中取出两个节点进行比较：

  1. 初始时将根节点的左右子节点入队；
  2. 循环取出队首的两个节点：
    • 若均为空，继续；
    • 若一个为空或值不等，返回false；
    • 将左节点的左子节点与右节点的右子节点入队；
    • 将左节点的右子节点与右节点的左子节点入队。
  3. 队列为空时返回true。

2. 代码实现

  1. function isSymmetricIterative($root) {
  2.     if ($root === null) return true;
  3.     $queue = new SplQueue();
  4.     $queue->enqueue($root->left);
  5.     $queue->enqueue($root->right);
  7.     while (!$queue->isEmpty()) {
  8.         $left = $queue->dequeue();
  9.         $right = $queue->dequeue();
  11.         if ($left === null && $right === null) continue;
  12.         if ($left === null || $right === null) return false;
  13.         if ($left->val != $right->val) return false;
  15.         $queue->enqueue($left->left);
  16.         $queue->enqueue($right->right);
  17.         $queue->enqueue($left->right);
  18.         $queue->enqueue($right->left);
  19.     }
  20.     return true;
  21. }

3. 迭代的优势

  • 空间效率：队列存储节点对，空间复杂度为O(n/2)（最坏情况下需存储半数节点）。
  • 稳定性：无递归栈溢出风险，适合生产环境。

四、性能优化与边界条件处理

1. 边界条件

  • 空树：直接返回true；
  • 单节点树：左右子节点均为空，返回true；
  • 不对称树：如左子树存在而右子树为空，需提前终止。

2. 优化方向

  • 剪枝：在递归中若发现不对称，立即返回，避免无效比较；
  • 内存复用：迭代方案中可复用队列对象，减少内存分配；
  • 并行化：对于超大规模树，可拆分左右子树为独立任务（需多线程支持）。

五、测试用例设计

验证代码正确性需覆盖以下场景：

  1. 空树：$root = null，预期true；
  2. 单节点树：$root = new TreeNode(1)，预期true；
  3. 对称树： 
    1. $root = new TreeNode(1);
    2. $root->left = new TreeNode(2);
    3. $root->right = new TreeNode(2);
    4. $root->left->left = new TreeNode(3);
    5. $root->left->right = new TreeNode(4);
    6. $root->right->left = new TreeNode(4);
    7. $root->right->right = new TreeNode(3);

    预期true；

  4. 非对称树： 
    1. $root = new TreeNode(1);
    2. $root->left = new TreeNode(2);
    3. $root->right = new TreeNode(2);
    4. $root->left->right = new TreeNode(3);
    5. $root->right->right = new TreeNode(3);

    预期false。

六、总结与最佳实践

  1. 递归适用场景：树深度较小（如百层以内），代码可读性优先；
  2. 迭代适用场景：树深度较大或需稳定运行的生产环境；
  3. 通用建议：
    • 优先使用迭代方案避免栈溢出；
    • 添加输入参数校验（如$root是否为TreeNode实例）；
    • 结合单元测试覆盖极端案例。

通过递归与迭代的双路径实现，开发者可灵活选择适合业务场景的方案，同时深入理解二叉树对称性判定的本质逻辑。

最新文章