题目描述

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

https://leetcode-cn.com/problems/symmetric-tree/

解法1

为了解决问题,我们先画一个比较general的case来帮助我们思考。我们构建一个4层的对称二叉树,如图1所示。我们可以发现,如果一颗树是对称二叉树,那么它的左子树与右子树是互为镜像的。如图1所示,跟节点root的左子树root.left与右子树root.right互为镜像。因此,我们可以把问题转化为判断两个二叉树是否互为镜像

图1 – 对称二叉树示例

为了判断两颗二叉树是否互为镜像,我们创建函数private boolean isMirror(TreeNode node1, TreeNode node2),用来判定两颗二叉树node1与node2是否互为镜像。那我们如何实现这个函数呢?

  • 首先,如果node1与node2都是空,很好理解,他们是镜像的。
  • 如果node1与node2有一个为空,另一个非空,那么肯定不是镜像的。
  • 如果node1与node2都非空,但是node对应的值不想相等,那么也不互为镜像。
  • 如果node1与node2非空,且值相等,那我们还需要递归的判断node1的右子树与node2的左子树互为镜像,且node1的左子树与node2的右子树互为镜像。

我们按照上面的规则递归的判定,直到我们都访问到叶节点后返回我们才能确定两棵树是互为镜像的。如果在递归的过程中发现有不符合上述规则都情况,那么这两棵树就不是镜像的。

下面的代码采用DFS方式判定,我们按照上面4条规则实现了isMirror函数,然后我们把root的左子树与右子树传递给isMirror函数就能够判定整棵树是否是对称的。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null)
            return true;
        else if (node1 == null || node2 == null)
            return false;

        return node1.val == node2.val &&
                isMirror(node1.left, node2.right) &&
                isMirror(node1.right, node2.left);
    }
}

解法2

解法2采用另一个比较直观的思路,比较容易理解。我们观察图1,如果树是对称的,那么我们横向读取每一层的节点,都会发现他们是“回文序列”,也就是从左到右读和从右到左读都是一样的。如果有任何一层读起来不是回文序列,那么这棵树就不是对称的!

为了实现按层次遍历,我们使用BFS算法,用一个队列来实现。但是队列没法随机访问,我们在实现时使用数组来模拟队列。如果使用数组的remove方法来出队,会涉及到元素移动,使得时间复杂度达到O(n^2)。因此,我们采用“双缓冲”方法,创建变量queue以及buffer,从queue中读取当前层到节点并访问,将下一层节点放入buffer,然后交换queue与buffer。如果你不清楚二叉树层次变量,可以参考这个

时间复杂度为O(n),空间复杂度为O(n)。全部代码如下:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> queue = new ArrayList<>();
        List<TreeNode> buffer = new ArrayList<>();

        if (root == null)
            return true;

        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            // 判断当前是否是回文序列
            for (int i = 0; i < size / 2; i++) {
                TreeNode front = queue.get(i);
                TreeNode end = queue.get(size - i - 1);

                if (front != null && end != null) {
                    if (front.val != end.val)
                        return false;
                } else if (front != null || end != null)
                    return false;
            }

            for (TreeNode node : queue) {
                if (node != null) {
                    buffer.add(node.left);
                    buffer.add(node.right);
                }
            }

            queue.clear();
            List<TreeNode> tmp = queue;
            queue = buffer;
            buffer = tmp;
        }

        return true;
    }
}
pwrliang Algorithms, BFS, DFS, Tree , ,

Leave a Reply

Your email address will not be published. Required fields are marked *