LeetCode 100 及 101题
100. 相同的树
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3 [1,2,3], [1,2,3] 输出: true
示例 2:
输入: 1 1
/ \
2 2 [1,2], [1,null,2] 输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2 [1,2,1], [1,1,2] 输出: false
源码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
else if(!(p != null && q != null))
return false;
else {
if(p.val == q.val)
return(isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
else
return false;
}
}
}
这道题我的解题思路是通过递归遍历这两个树。当两个树当前的节点对应的值相等时,调用自己的方法判断当前节点的左右两个子树是不是也是相同的树,递归终止的条件就是:如果两个树的当前节点都为空,返回true;一个树为空一个不为空,返回false;当前节点的值不相同,也返回false。
101. 对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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) {
if(root == null)
return true;
else
return isMirror(root.left, root.right);
}
public boolean isMirror(TreeNode m, TreeNode n) {
if(m == null & n == null)
return true;
else if(m !=null && n !=null && m.val == n.val)
return (isMirror(m.left, n.right) && isMirror(m.right, n.left));
else
return false;
}
}
执行用时 : 1 ms, 在Symmetric Tree的Java提交中击败了99.59% 的用户
内存消耗 : 34.8 MB, 在Symmetric Tree的Java提交中击败了85.06% 的用户
按照题目要求,还可以用循环的方法做这道题。我的思路是,设定两个 List,分别代表从根节点分开的左边的树和右边的树,在设定两个 int 类型变量作为 List 的光标(index),将两个子树的头加入 List 中。循环体中:当两个树对应节点处的值相等,则将左边树的左、右子节点依次加入 List1,对应的将右边树的右、左子节点;依次加入 List2,然后两个光标自加;若对应节点都为空,则光标自加,然后 continue 继续下一次循环;若只有一个为空,返回 false;其他情况也返回 false。循环的终止条件是,光标的值不小于 List 的长度了,也就是任意一个 List 的每个元素已经循环完了。若循环结束,最后此方法返回 true。
/**
* 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) {
if (root == null)
return true;
List<TreeNode> l1 = new ArrayList<TreeNode>();
List<TreeNode> l2 = new ArrayList<TreeNode>();
l1.add(root.left);
l2.add(root.right);
int cur1 = 0;
int cur2 = 0;
while(cur1 < l1.size() && cur2 < l2.size()) {
if(l1.get(cur1) == null && l2.get(cur2) == null) {
cur1++;
cur2++;
continue;
}
else if(l1.get(cur1) == null || l2.get(cur2) == null)
return false;
else if(l1.get(cur1).val == l2.get(cur2).val) {
l1.add(l1.get(cur1).left);
l1.add(l1.get(cur1++).right);
l2.add(l2.get(cur2).right);
l2.add(l2.get(cur2++).left);
}
else
return false;
}
return true;
}
}
执行用时 : 3 ms, 在Symmetric Tree的Java提交中击败了64.39% 的用户
内存消耗 : 34.6 MB, 在Symmetric Tree的Java提交中击败了88.39% 的用户
最新文章
- PHPExcel导出数据
- 034. asp.netWeb用户控件之三通过用户控件实现用户注册和登录
- [转]非OpenVZ下利用谷歌TCP-BBR协议单边加速你的VPS
- Learn clojure in Y minutes
- spring之bean的作用域scope的值的详解
- hdoj 1532 Drainage Ditches【最大流模板题】
- ORA-12516 TNS监听程序找不到符合协议堆栈要求的可用处理程序
- 打包apk java 虚拟机内存不足
- vue mint UI
- hashmap简单实例(个人使用经验)
- Missing artifact com.oracle:ojdbc6:jar:11.2.0.3 Maven中不能引入ojdbc解决方法,错误
- PHP会员找回密码功能实现实例介绍
- poj 2074
- Ajax实战(原生)
- 2017-2018-2 20155309南皓芯 Exp6 信息搜集与漏洞扫描
- Github安卓开源项目编译运行
- js中setTimeout和clearTimeout的使用
- lvalue require as increment operand
- jenkins 修改工作目录
- 优化 JS 条件语句的 5 个技巧