【力扣题解】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;
}

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

🌏总结

这个题其实是对树的两个子树进行遍历，首先我们要明确一棵二叉树要满足哪些条件它会是对称二叉树：

• 左右子树为空
• 左孩子节点等于右孩子节点
• 左子树的左孩子节点等于右子树的右孩子节点，左子树的右孩子节点等于右子树的左孩子节点

根据以上三个条件我们就可以写出对应的递归算法。

同样，迭代法也是如此，对应迭代法，我们采用一个队列，首先将树的左右子树节点进队，然后对这两个节点进行以上三点判断，再将他们的左右子树对应的节点入队，如此循环，便可以判断树是否是对称的。

作者：花无缺(huawuque404.com)

---

🌸欢迎关注我的博客：花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏：【力扣题解】
🥇往期精彩好文：
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏⭐ 留言📝 关注✅
是我持续创作，输出优质内容的最大动力！
谢谢！

这篇关于【力扣题解】P101-对称二叉树-Java题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---