【力扣题解】P101-对称二叉树-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P101-对称二叉树-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P101-对称二叉树-Java题解

P101.对称二叉树

🌏题目描述

给你一个二叉树的根节点 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

💡题解

递归法：

public boolean isSymmetric(TreeNode root) {
    return recur(root.left, root.right);
}
// 深度优先搜索, 递归法
// 递归终止条件:
// 1.两个节点都为空
// 2.仅有一个节点为空
// 3.两个节点的值不相等
public boolean recur(TreeNode L, TreeNode R) {
    // 两个节点都为空
    if (L == null && R == null) {
        return true;
    }
    // 仅有一个节点为空
    if (L == null || R == null) {
        return false;
    }
    // 两个节点的值不相等
    if (L.val != R.val) {
        return false;
    }
    // 如果当前两个对应的节点是对称的, 那么递归判断这两个节点对应的左右孩子节点是否对称
    return recur(L.left, R.right) && recur(L.right, R.left);
}

算法数据复杂度：O(n)，需要遍历树的所有节点，节点数为 n。

迭代法：

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    // 首先将根节点的左右孩子入队
    queue.offer(root.left);
    queue.offer(root.right);
    while (!queue.isEmpty()) {
        // 将队头两个节点出队
        TreeNode l = queue.poll();
        TreeNode r = queue.poll();
        // 如果两个节点都为空, 判断下一对节点
        if (l == null && r == null) {
            continue;
        }
        // 如果仅有一个节点为空, 说明不是对称的
        if (l == null || r == null) {
            return false;
        }
        // 如果两节点值不相等也不对称
        if (l.val != r.val) {
            return false;
        }

        // 将左节点的左孩子和右节点的右孩子入队
        // 之后进行判断
        queue.offer(l.left);
        queue.offer(r.right);

        // 将左节点的右孩子和右节点的左孩子入队
        // 之后进行判断
        queue.offer(l.right);
        queue.offer(r.left);
    }
    return true;
}