轴对称二叉树判定：递归与迭代方法解析

对称二叉树是一种特殊的二叉树结构，其中树的左半部分和右半部分关于根节点对称。判断一个二叉树是否为对称二叉树是算法设计中的经典问题，主要用于考察递归和迭代这两种数据结构和算法技巧的应用。 **1. 题目描述** 题目要求我们给定一个二叉树的根节点 `root`，判断这棵树是否是轴对称的。轴对称意味着树的左半部分与右半部分在根节点处是对称的，即除了根节点外，对应位置的节点值相等，并且它们的左右子树也分别是对称的。比如，示例1的二叉树 [1,2,2,3,4,4,3] 是对称的，而示例2的 [1,2,2,null,3,null,3] 不是。 **2. 解决方法** **方法一：递归** 递归是一种直观且常见的解决方法。通过定义一个名为 `isSymmetric` 的递归函数，使用两个指针 `pp` 和 `qq` 同步移动，每次检查当前节点的值是否相等以及它们的子树是否对称。如果满足条件，递归地检查左右子节点。递归的时间复杂度为 O(n)，空间复杂度为 O(n)，因为最坏情况下递归深度等于树的高度。 ```java class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); } private boolean check(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && check(p.left, q.right) && check(p.right, q.left); } } ``` **方法二：迭代** 为了减少递归带来的栈空间消耗，可以采用迭代的方式实现。这里使用一个队列来模拟递归过程，初始时将根节点及其自身入队。然后每次从队列中取出一对节点进行比较，如果值相等并且子树对称，则继续检查下一对节点；否则返回 false。当队列为空时，表示所有节点都已检查，树是轴对称的。这种方法同样具有 O(n) 的时间复杂度，但空间复杂度降低到了 O(1)。 ```java public boolean isSymmetric(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); queue.offer(root); while (!queue.isEmpty()) { TreeNode p = queue.poll(); TreeNode q = queue.poll(); if (p == null && q == null) continue; if (p == null || q == null || p.val != q.val) return false; queue.offer(p.left); queue.offer(q.right); queue.offer(p.right); queue.offer(q.left); } return true; } ``` 总结起来，对称二叉树的判断问题主要涉及递归或迭代的思路，通过比较节点值和检查子树对称性来确定整个树是否满足轴对称条件。在实际编程中，选择哪种方法取决于性能需求、代码简洁性和可读性等因素。理解这两种方法有助于深入掌握二叉树的遍历和结构特性。