讨论/技术交流/小哥哥们,问一下我哪里写错了/
小哥哥们,问一下我哪里写错了

第100.相同二叉树,我最开始用的很麻烦的BFS,并且存储在一个list中,我不存list的bfs和dfs都过了,但这个最初版本总是有两个测试用例过不了。

public boolean isSameTree(TreeNode p, TreeNode q) {
    //判空
    if(p==null&&q==null) return true;
    //两个queue,分别用来遍历两个树
    Queue<TreeNode> queue1=new LinkedList<>();
    Queue<TreeNode> queue2=new LinkedList<>();
    //两个List,分别用来存储遍历结果
    List<Integer> list1=new ArrayList<>();
    List<Integer> list2=new ArrayList<>();
    queue1.add(p);
    queue2.add(q);
    while(!queue1.isEmpty()){
        TreeNode node=queue1.poll();
        if(node!=null){
            //取queue的头,如果为空则在list中加入这个节点的值
            list1.add(node.val);
            //如果左孩子不为null就在queue中加左孩子,否则加个null
            if(node.left!=null) queue1.add(node.left);
            else queue1.add(null);
            if(node.right!=null) queue1.add(node.right);
            else  queue1.add(null);
        }  
        //如果queue出来的是null,就在list中加个null
        else list1.add(null);
    }
    while(!queue2.isEmpty()){
        TreeNode node=queue2.poll();
        if(node!=null){
            list2.add(node.val);
            if(node.left!=null) queue2.add(node.left);
            else queue2.add(null);
            if(node.right!=null) queue2.add(node.right);
            else  queue2.add(null);
        }else list2.add(null);
    }
    //如果两个list大小不一样,则肯定不一样
    if(list1.size()!=list2.size())
        return false;
    //遍历两个list,逐个比较
    for(int i=0;i<list1.size();i++){
        if(list1.get(i)==list2.get(i))
            continue;
        else if(list1.get(i)!=list2.get(i)) return false;
    }
    return true;
}
共 4 个回复

如果是这种思路,建议参考“二叉树的序列化“
不仅比较有值的,也要比较null的结点

样例过不了,建议你把结果也贴一下。

目测两个 Integer 类型的引用不相同。 == 比较的两个Integer的引用而非值。你打印看下 两个Integer的hashcode 看是不是相等

update:2020.03.10 19:12

Integer 内部有缓存,默认情况下-128~127 的值直接复用,范围外创建新对象。== 比较的两个对象的引用即 hashcode

相关Integer 源码:

public static Integer valueOf(int i) {
		//IntegerCache.low = -128  IntegerCache.high=127
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }


问问题时候最好把代码注释下。。。