对称二叉数[简单]

优质博文：IT-BLOG-CN

一、题目

给你一个二叉树的根节点root，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

树中节点数目在范围[1, 1000]内
-100 <= Node.val <= 100

进阶： 你可以运用递归和迭代两种方法解决这个问题吗？

二、代码

【1】递归： 我们将一个树的左右节点相同，转换为两个根节点具有相同的值，每个树的右子树都与另一个树的左子树镜像对称。我们通过一个递归函数，通过同步移动两个指针的方式来遍历树，rootLeft和rootRight都指向一个树的根，然后rootLeft右移时，rootRight左移，rootLeft左移时，rootRight右移。检查rootLeft和rootRight的值是否相等，如果相等再判断左右子树是否对称。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    private boolean check(TreeNode rootLeft, TreeNode rootRight) {
        if (rootLeft == null && rootRight == null) {
            return true;
        }
        if (rootLeft == null || rootRight == null) {
            return false;
        }
        return rootLeft.val == rootRight.val && check(rootLeft.left, rootRight.right) && check(rootLeft.right, rootRight.left);
    }
}
**时间复杂度：** 这里遍历了这棵树，渐进时间复杂度为`O(n)`。  
**空间复杂度：** 这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过`n`，故渐进空间复杂度为`O(n)`。

【2】迭代： 我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    private boolean check(TreeNode rootLeft, TreeNode rootRight) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(rootLeft);
        q.offer(rootRight);
        while(!q.isEmpty()) {
            rootLeft = q.poll();
            rootRight = q.poll();
            if (rootLeft == null && rootRight == null) {
                continue;
            }
            if ((rootLeft == null || rootRight == null) || (rootLeft.val != rootRight.val)) {
                return false;
            }
            q.offer(rootLeft.left);
            q.offer(rootRight.right);

            q.offer(rootLeft.right);
            q.offer(rootRight.left);
        }
        return true;
    }
}