LeetCode 101
2020.8.12
我的通过代码
/**
* 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) {
List<Integer> list = new ArrayList<Integer>();
return traverse(root,root);
}
boolean traverse(TreeNode root,TreeNode root2) {
if(root==null&root2==null) return true;
if(root==null||root2==null) return false;
return (root.val==root2.val)&&(traverse(root.left,root2.right))&&(traverse(root.right,root2.left));
}
}
碰上的问题
这次碰上的问题老多了，一个一个的说。
菜，就是原罪！
1.中序遍历
处理这道题目，一开始我想的太简单，打算用中序遍历把二叉树遍历一遍，把每个节点的值存在集合里，再去进行回文判断，然后我遇到了这样的树：
[1,2,2,null,2,null,2]
emmmm
中序遍历无法确认一棵树的形状。同样的中序遍历结果可能对应不同树。
2.Integer比较
可我还是头铁，就是想用中序遍历解决这道题，于是我想在最后一层补上那些缺的节点，并给他们赋一个较特别的值以便进行比较，比如把null变成1000。这样一来上面那棵树就会变成这样：
这样一来，它的中序遍历序列就会变成 [1000,2,2,1,1000,2,2]，好像就可以判断出这不是对称的二叉树了。
于是，我开始暴力编码，代码如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
traverse(root,list);
boolean flag = true;
for(int i=0;i<list.size()/2;i++) {
if(list.get(i) != list.get(list.size()-i-1) ) {
flag = false;
break;
}
}
return flag;
}
void traverse(TreeNode root,List<Integer> list) {
if(root==null) return;
if(root.left!=null&&root.right!=null) {
traverse(root.left,list);
list.add(root.val);
traverse(root.right,list);
}
else if(root.left!=null&&root.right==null) {
traverse(root.left,list);
list.add(root.val);
list.add(1000);
}
else if(root.left==null&&root.right!=null) {
list.add(1000);
list.add(root.val);
traverse(root.right,list);
}
else if(root.left==null&&root.right==null){
list.add(root.val);
}
}
}
可是当我测试一个对称的用例时，又出问题了。
[1,2,2,null,3,3]
对于这个输入，list集合记录的元素序列也的确为[1000,2,3,1,3,2,1000]，可是最后的输出却是false。
在我一一打桩输出之后，发现list.get(0)和list.get(6)，也就是这个集合的头尾两个1000元素进行比较时，输出的结果是false。不失一般性，我又比较了list.get(1)和list.get(5)，也就是第二个和倒数第二个元素，输出结果是true。
这可奇了怪了，一样的整数还能不相等吗？
原来，问题出在了类型上。我们可以看一看下面这两种代码：
int a,b;
a=1000;b=1000;
Integer x,y;
x=1000;y=1000;
a和b为int型变量，其取值范围在-2147483648~2147483647间，相比之下1000是个非常普通的数，a和b的比较自然也没有问题。
可是，x和y呢？查找资料后，我发现：
java中Integer类型对-128~127之间的数是在缓冲区取得的，因此可以用“=”直接进行比较；而对于不在这个区间内的数字，Integer是在堆中new出来的，它们的地址空间不一样，自然不能用“=”进行比较。
所以，在对Integer类型进行比较时，还是使用intValue()方法比较好。
emmmmm
言归正传，解决了这一问题之后，提交还是没通过。这次被这样的输入卡住了：
[5,4,1,null,1,null,4,2,null,2,null]
看来在需要考虑树的结构问题时，中序遍历的确不是一个好的方法。
PS：这一题的评论区有个人和我思路差不多，但他是把我置为1000的空节点全部用该节点所在的层数的相反数来表示，看起来效果不错。