力扣第一百零一题-对称二叉树 前言 一、思路 二、实现 三、

发表于

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

前言

力扣第一百零一题 对称二叉树 如下所示：

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

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

1
2
3
4
5
markdown复制代码    1
   / \
  2   2
 / \ / \
3  4 4  3

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

1
2
3
4
5
markdown复制代码    1
   / \
  2   2
   \   \
   3    3

一、思路

题目中有一个关键信息：镜像对称。

那什么是镜像对称呢？就是指 根节点的左孩子 left 与右孩子 right相同，且 left.left == right.right 相同，left.right == right.left。如下图所示：

image.png

所以我们可以从根节点出发，到达根节点的左孩子 left 和右孩子 right，如果值相同则继续比对 left.left 是否与 right.right 相等，再比对 left.right 和 right.left 即可。

因为每一个节点都有可能是一个子树，所以我们这里使用递归是一个不错的选择，就不用手动去维护栈了。

在递归中我们要处理一些特殊的边界情况，如下所示：

  1. 如果根节点为空 null，则直接返回 true 即可。（空节点我们认为也是镜像对称的）
  2. 如果 left == right == null，也可以返回 true（两个空节点是相等的）
  3. 如果 left 和 right 中只有一个为空，此时返回 false（很显然空节点不等于有值的节点）

举个例子

我们以下方的树作为例子：

image.png

  1. 对比根节点的左孩子，相等则继续向下

image.png

  1. 继续对比子树 left 的左孩子和子树 right 的右孩子，发现 5 != 3，则表示这个树不为镜像对称

image.png

  1. 找到结果后，直接返回 false 即可

二、实现

实现代码

实现代码与思路中保持一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java复制代码    public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        return dfs(root.left, root.right);
    }

    public boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        else if (left == null || right == null)
            return false;
        else if (left.val != right.val)
            return false;
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }

测试代码

1
2
3
4
5
6
7
java复制代码    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1,
                new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                new TreeNode(2, new TreeNode(4), new TreeNode(3)));
        boolean flag = new Number101().isSymmetric(treeNode);
        System.out.println(flag);
    }

结果

image.png

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%