LVS elasticsearch webpack webview uiview eking文件 arduino grunt jq获取第一个子元素 安卓程序源代码 查看mysql是否启动 python关键字 python的def python如何定义变量 java集成 java入门教程 java正则表达式详解 java中tostring方法 java实现队列 java怎么获取当前时间 脚本之家 phpqrcode navicat注册机 ps选择反向快捷键 电脑手机模拟器 七宗罪游戏下载 3d软件下载 pdf安装包官方下载 微信砍价活动怎么做 京东钱包客户端 bz2 扫微信二维码诈骗原理 大势至usb监控 js切割字符串 jq改变css样式 鬼灵战马 夜之魇掉落 top命令详解 vue动态路由 狂战传说套装选择
当前位置: 首页 > 学习教程  > 编程语言

LeetCode对称二叉树

2021/1/13 20:40:51 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 1/ \2 2/ \ / \3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1/ \ 2 2 \ \3 3请用递归和非递归两种方法解…

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

      1
   /     \
   2       2
  / \     / \
 3  4     4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

   1
 /    \
2      2
\       \
  3      3

请用递归和非递归两种方法解决问题。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 	public boolean isSymmetric(TreeNode root) {

    }
}

这种题第一印象是什么?拿到后应该怎么做?

我的第一印象,是分别让根节点的左右两个孩子分别作为一颗新的树,然后按照一定的方式遍历,对比二者的值,判断是否相等。天不遂人愿,总有测试样例通过不了。细究,是因为遍历出来的值顺序并不一定和原始的排序顺序相等。看如下用例:

        1
    /      \
   2        2
  /         / 
  2        2

它并不对称,但是遍历出的子树均为[2,2],如果将null值也记录起来,则不得不记录当前节点的层数。只有当这一层有其他节点非空的时候,才会将这一层的值都记录下来。是不是太麻烦了,这毕竟是个简单题。

再审视一下树的结构:

	   1
	/     \
   2       2
  / \     / \
 3  4     4  3

当我们对比的时候,比较的是root.leftroot.right,然后比较root.left.leftroot.right.rightroot.left.rightroot.right.left。如果树再高点,就是继续划分。但是用代码可以写成:

if(root.left == root.right)
	left = root.left
	right = root.right
if(left.left== right.right && left.right == right.left)
	leftl = left.left
	leftr = left.right
	rightl = right.left
	rightr = right.right
if(...)

有点递归的意思了。

那我们先写一个比较代码:

boolean cmp(TreeNode a, TreeNode b){
	if(a != null && b!= null){
		if(a.val != b.val){
			return false;
		}
		if(a.val == b.val){
			return true;
		}
	}else if(a== null && b == null){
		return true;
	}else{
		return false;
	}
}

然后我们看看递归应该往哪放。
递归必然是在上一层都相等的情况下判断下一层是否相等,否则直接跳出即可。

boolean cmp(TreeNode a, TreeNode b){
	if(a != null && b!= null){
		if(a.val != b.val){
			return false;
		}
		if(a.val == b.val){
			return cmp(a.left, b.right) && cmp(a.right, b.left);
		}
	}else if(a== null && b == null){
		return true;
	}else{
		return false;
	}
}

全部代码如下:

class Solution {
   boolean cmp(TreeNode a, TreeNode b){
	if(a != null && b!= null){
		if(a.val != b.val){
			return false;
		}
		if(a.val == b.val){
			return cmp(a.left, b.right) && cmp(a.right, b.left);
		}
	}else if(a== null && b == null){
		return true;
	}
	return false;
	
}
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        return cmp(left, right);
    }
}

非递归怎么写?

之前我说,可能要记录层数才能做到按照某种顺序(如中序)输出,但是这样还不行。我们知道,仅靠中序遍历是不能得到一个树的,可能许多不同的树中序遍历后都是一个顺序。所以只能另想它法。

既然存值不行,那我们就存节点。将节点按照某种顺序存进数组中,再判断两个数组是否是相同值。

class Solution {
  
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> left = new LinkedList<TreeNode>();
        Queue<TreeNode> right = new LinkedList<TreeNode>();

        if(root == null){
            return true;
        }
        if(root.left == null && root.right == null){
            return true;
        }
        if(root.left == null || root.right == null){
            return false;
        }
        if(root.left != null && root.right != null){
            left.offer(root.left);
            right.offer(root.right);
        }
        
        while(!left.isEmpty() && !right.isEmpty()){
            TreeNode l = left.poll();
            TreeNode r = right.poll();

            if(l == null && r == null){
                continue;
            }
            if(l != null && r != null && l.val != r.val){
                return false;
            }
            if(l == null || r == null){
                return false;
            }
            
            left.offer(l.left);
            left.offer(l.right);

            right.offer(r.right);
            right.offer(r.left);
        }
        return true;
    }
}

本文链接: http://www.dtmao.cc/news_show_600398.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?