题目详情

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

示例 1：

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

       1
     /   \
    2     2
   / \    / \
  3   4  4   3

Java代码（递归）

public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    //从两个子节点开始判断
    return isSymmetricHelper(root.left, root.right);
}

public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
    //如果左右子节点都为空，说明当前节点是叶子节点，返回true
    if (left == null && right == null)
        return true;
    //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
    if (left == null || right == null || left.val != right.val)
        return false;
    //然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
    return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}

总结

递归的结束条件是遇到了叶子节点，并且左右的叶子节点都为null，如果只有一个叶子节点为null那么说明不是镜像，那么直接返回false，或者传入的left和right的值不相等，那么返回false。然后再判断左子树和右子树是否同时满足镜像的条件。

Java代码（队列）

public boolean isSymmetric(TreeNode root) {
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null)
        return true;
    //左子节点和右子节点同时入队
    queue.add(root.left);
    queue.add(root.right);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //每两个出队
        TreeNode left = queue.poll(), right = queue.poll();
        //如果都为空继续循环
        if (left == null && right == null)
            continue;
        //如果一个为空一个不为空，说明不是对称的，直接返回false
        if (left == null ^ right == null)
            return false;
        //如果这两个值不相同，也不是对称的，直接返回false
        if (left.val != right.val)
            return false;
        //这里要记住入队的顺序，他会每两个两个的出队。
        //左子节点的左子节点和右子节点的右子节点同时
        //入队，因为他俩会同时比较。
        //左子节点的右子节点和右子节点的左子节点同时入队，
        //因为他俩会同时比较
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}

总结

使用队列的性质， 先将根节点的左右节点插入队列，然后遍历队列，这里要注意，入队时要先插入左节点再插入右节点，在遍历中，先出队两个节点，如果都为空就继续循环，如果两个值不同或者一个为空就返回false。然后再将这两个节点的子节点入队，这时候我们需要注意入队的顺序，因为我们在遍历出队的时候是比较左右两个节点，那么入队的时候就需要先入队左节点的左节点，和右节点的右节点，就是子树的两边的节点，然后再入队中间的两个节点。