例如： 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围：节点数满足 
，节点上的值满足 
要求：空间复杂度 )
，时间复杂度
备注：
你可以用递归和迭代两种方法解决这个问题
[编程题]对称的二叉树
层序遍历实现，不够优雅，时间复杂度logN,建议参考讨论中大神代码；
递归实现太难想了，还是菜。。。。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return bool布尔型
*/
public boolean isSymmetrical (TreeNode pRoot) {
// write code here
LinkedList<TreeNode> queue = new LinkedList<>();
// 根节点为空或者只有一个根节点返回true
if (pRoot == null || pRoot != null && pRoot.left == null &&
pRoot.right == null ) {
return true;
}
if (pRoot != null) {
boolean pl = this.exists(pRoot.left);
boolean pr = this.exists(pRoot.right);
if (pl && pr && pRoot.left.val == pRoot.right.val) {
queue.push(pRoot.left);
queue.push(pRoot.right);
} else {
return false;
}
}
TreeNode left;
TreeNode right;
while (!queue.isEmpty()) {
left = queue.poll();
right = queue.poll();
boolean ll = this.exists(left.left);
boolean lr = this.exists(left.right);
boolean rl = this.exists(right.left);
boolean rr = this.exists(right.right);
if (ll && rr || !ll && !rr) {
if (ll) {
if (left.left.val == right.right.val) {
queue.add(left.left);
queue.add(right.right);
} else {
return false;
}
}
} else {
return false;
}
if ( lr && rl || !lr && !rl) {
if (lr ) {
if (left.right.val == right.left.val) {
queue.add(left.right);
queue.add(right.left);
} else {
return false;
}
}
} else {
return false;
}
}
return true;
}
private boolean exists(TreeNode node) {
return node != null;
}
}
编辑于 2024-01-11 17:40:08
回复(0)
直接遍历左右子树，如果
(left==null&&right!=null)||(left!=null&&right==null)||(right.val!=left.val)
则为false，不对称；如果left==null&&right==null则为true 对称， 然后递归比对子节点的右子节点和有子节点的左子节点，左子节点的左子节点和右子节点的右子节点
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return bool布尔型
*/
public boolean isSymmetrical (TreeNode pRoot) {
// write code here
if(pRoot==null){
return true;
}
return isSymme(pRoot.left,pRoot.right);
}
public boolean isSymme(TreeNode left,TreeNode right){
if(left==null&&right==null){
return true;
}
if((left==null&&right!=null)||(left!=null&&right==null)||(right.val!=left.val)){
return false;
}
return isSymme(left.right,right.left)&&isSymme(left.left,right.right);
}
}
发表于 2023-11-30 10:54:00
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return bool布尔型
*/
boolean b=true;
public boolean isSymmetrical (TreeNode pRoot) {
// write code here
if(pRoot==null)
return true;
a(pRoot.left,pRoot.right);
return b;
}
public void a(TreeNode left,TreeNode right){
if(left==null&&right==null)
return;
if(left==null||right==null){
b=false;
return;
}
if(left.val!=right.val){
b=false;
return;
}
a(left.left,right.right);
a(left.right,right.left);
}
}
发表于 2023-10-12 09:46:41
回复(1)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return bool布尔型
*/
public boolean isSymmetrical (TreeNode pRoot) {
// write code here
if (pRoot == null) {
return true;
}
return isSymbol(pRoot.left, pRoot.right);
}
public boolean isSymbol (TreeNode left, TreeNode right) {
// 同时为空，对称
if (left == null && right == null) {
return true;
}
// 不同时为空，有一个为空，不对称
if (left == null || right == null) {
return false;
}
// 同时不为空，值不相等，不对称
if (left.val != right.val) {
return false;
}
return isSymbol(left.left, right.right) && isSymbol(left.right, right.left);
}
}
发表于 2023-08-15 11:12:32
回复(0)
//思路：对称及子树的左子树等于子树的右子树
public boolean isSame(TreeNode r1,TreeNode r2) {
if(r1==null&&r2==null) {
return true;
}
if(r1==null||r2==null) {
return false;
}
if(r1.val!=r2.val) {
return false;
}
//让r1的左与r2的右进行比较，r1的右与r2的左进行比较
return isSame(r1.left,r2.right)&&isSame(r1.right,r2.left);
}
public boolean isSymmetrical (TreeNode pRoot) {
if(pRoot==null) {
return true;
}
return isSame(pRoot.left,pRoot.right);
}
发表于 2023-07-14 13:48:57
回复(0)
public boolean isSymmetrical (TreeNode pRoot) {
if(pRoot==null) return true;
boolean ans=build(pRoot.left,pRoot.right);
return ans;
}
public boolean build(TreeNode left,TreeNode right){
if(left==null&&right==null) return true;
if(left==null&&right!=null) return false;
if(left!=null&&right==null) return false;
if(left.val!=right.val) return false;
boolean leftB=build(left.left,right.right);
boolean rightB=build(left.right,right.left);
return leftB&&rightB;
}
发表于 2023-07-12 11:47:29
回复(0)
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null) {
return true;
}
return isSymmetrical(pRoot.left, pRoot.right);
}
private boolean isSymmetrical(TreeNode left, TreeNode right) {
if (left == null) {
return right == null;
}
if (right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return isSymmetrical(left.left, right.right) &&
isSymmetrical(left.right, right.left);
}
}
发表于 2022-11-07 12:12:52
回复(0)
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null)return true;
return compare(pRoot.left,pRoot.right);
}
public boolean compare(TreeNode leftNode,TreeNode rightNode){
if(leftNode==null && rightNode == null)return true;
else if(leftNode != null && rightNode==null)return false;
else if(leftNode ==null && rightNode!=null)return false;
else if(leftNode.val!=rightNode.val)return false;
boolean in = compare(leftNode.left,rightNode.right);
boolean out = compare(leftNode.right,rightNode.left);
return in && out;
}
}
发表于 2022-11-05 17:15:28
回复(0)
递归查找
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
// 非空验证
if(pRoot == null) return true;
// 开始递归查找
return isSymmetrical1(pRoot.left, pRoot.right);
}
boolean isSymmetrical1(TreeNode left, TreeNode right) {
// 左，右都为null则返回true
if(left == null && right == null) return true;
// 只有一个为null，就返回false
else if(left == null || right == null) return false;
// 两个值 不相等 则返回false
else if(left.val != right.val) return false;
// 运行到此，说明当前两个节点的值相等
// 下面分别左右递归 查找子节点是否相等，必须左右都返回true，否则false
return isSymmetrical1(left.left, right.right) && isSymmetrical1(left.right, right.left);
}
}
发表于 2022-11-04 20:09:11
回复(0)
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null || (pRoot.left == null && pRoot.right == null))
return true;
if (pRoot != null && (pRoot.left == null || pRoot.right == null))
return false;
if (pRoot.left.val != pRoot.right.val) {
return false;
} else {
return help(pRoot.left, pRoot.right);
}
}
boolean help(TreeNode left, TreeNode right) {
if (left == null && right == null)
return true;
if (left == null || right == null)
return false;
if (left.val == right.val)
return help(left.left, right.right) && help(left.right, right.left);
return false;
}
}
发表于 2022-09-29 09:23:52
回复(0)
public class Solution {
boolean isSymmetrical(TreeNode root) {
if(root == null) return true;
return dfs(root.left, root.right);
}
boolean dfs(TreeNode root1, TreeNode root2){
if(root1== null && root2 == null) return true;
if(root1 == null || root2 == null) return false;
return root1.val == root2.val && dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
}
}
发表于 2022-09-03 10:09:45
回复(0)
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null) return true;
return judge(pRoot.left, pRoot.right);
}
public boolean judge(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null || left.val != right.val) return false;
return judge(left.left, right.right) && judge(left.right, right.left);
}
}
发表于 2022-08-26 10:32:18
回复(0)
链表+二叉树实现
特点：堆成二叉树的中序遍历列表，也是一个堆成的列表，所以可以对二叉树进行一次中序遍历，再对遍历结果列表进行判断是否对称；
判断方法：列表判断是否对称，使用双指针，左右指针，判断链表是否对称；
注意：对称二叉树的根节点下，左右子节点的值必须一样，其他节点不需要，否则会出现如下情况的对称列表，但不是对称二叉树。
1
/ \
2 3
/ /
3 2
/ \
2 3
/ /
3 2
发表于 2022-06-26 20:39:29
回复(0)
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null){
return true;
}
return dfs(pRoot.left ,pRoot.right);
}
boolean dfs(TreeNode left,TreeNode right){
if(left==null && right==null){
return true;
}
if(left==null || right==null){
return false;
}
if(left.val!=right.val){
return false;
}
return dfs(left.left,right.right) && dfs(left.right ,right.left);
}
发表于 2022-06-19 15:25:55
回复(0)
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot ==null) return true;
return my(pRoot.left, pRoot.right);
}
boolean my(TreeNode left, TreeNode right){
if(left ==null && right==null) return true;
if(left ==null) return false;
if(right ==null) return false;
if(left.val != right.val) return false;
return my(left.left,right.right) && my(left.right,right.left);
}
发表于 2022-06-11 12:17:27
回复(0)
问题信息
通过挑战的用户
-
2023-02-21 16:04:31 -
2023-02-13 22:11:16 -
2022-10-16 16:18:27
-
2022-09-16 21:04:24 -
2022-09-16 18:19:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同 * 左子树的右子树和右子树的左子树相同即可，采用递归 * 非递归也可，采用栈或队列存取各级子树根节点 */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null){ return true; } return comRoot(pRoot.left, pRoot.right); } private boolean comRoot(TreeNode left, TreeNode right) { // TODO Auto-generated method stub if(left == null) return right==null; if(right == null) return false; if(left.val != right.val) return false; return comRoot(left.right, right.left) && comRoot(left.left, right.right); } }