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

本文主要是介绍【力扣题解】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;
}