☆打卡算法☆LeetCode 101、对称二叉树 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定二叉树的根节点，检查它是否轴对称。”

题目链接：

来源：力扣（LeetCode）

链接：101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

二、解题

1、思路分析

这道题是检查二叉树是否轴对称，如果这个树的左右子树镜像对称，那么这个树是对称的。

因此，可以将问题转化为，两个树在什么条件下互为镜像：

• 两个跟节点具有相同的值。
• 每个树的右子树都与另一个树的左子树镜像对称。

那么就可以编写一个递归函数，通过两个指针来遍历这棵树，指针开始都指向树的根，随后p指针向右，q指针向左；q指针向右，p指针向左。

每次先检查节点的值是否相同，再判断左右子树是否对称。

2、代码实现

代码参考：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public 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);
    }
}

3、时间复杂度

时间复杂度 ： O(n)

遍历了这棵树，时间复杂度为O(n)。

空间复杂度： O(n)

递归层数不超过n，空间复杂度为O(n)。

三、总结

我们使用递归的方法实现了对对称性的判断。

首先，判断根节点的值，然后判断左右子树的值是否相等，然后判断结构是否相同。