文档章节

判断两树是否相等 Same Tree

叶枫啦啦
 叶枫啦啦
发布于 2017/08/11 20:55
字数 245
阅读 13
收藏 0

问题:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

解决:

① 按使用DFS递归遍历,然后判断根节点,左右子树是否相等即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution { // 0ms
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

② 非递归方法,使用队列。

public class Solution{ //1ms
    public boolean isSameTree(TreeNode p, TreeNode q) {    
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();  
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();                    
        q1.offer(p);  
        q2.offer(q);    
        while( !q1.isEmpty() && !q2.isEmpty() ) {  
            TreeNode x = q1.poll();  
            TreeNode y = q2.poll();    
            if(x==null) {  
                if( y!=null) return false;  
                else continue;  
            }   
            if(y==null || x.val!=y.val) return false;  
            q1.offer( x.left);  
            q1.offer( x.right);  
            q2.offer(y.left);  
            q2.offer(y.right);  
        }  
        return true;  
    }  
}

© 著作权归作者所有

叶枫啦啦
粉丝 16
博文 583
码字总数 400448
作品 0
海淀
私信 提问

暂无文章

如何递归计算目录中的所有代码行?

我们有一个PHP应用程序,并希望计算特定目录及其子目录下的所有代码行。 我们不需要忽略评论,因为我们只是想弄清楚。 wc -l *.php 该命令在给定目录中运行良好,但忽略子目录。 我当时认为...

技术盛宴
39分钟前
4
0
使用 try-with-resources 优雅关闭资源

我们知道,在 Java 编程过程中,如果打开了外部资源(文件、数据库连接、网络连接等、redis),我们必须在这些外部资源使用完毕后,手动关闭它们。 因为外部资源不由 JVM 管理,无法享用 JVM ...

七弦桐
46分钟前
4
0
04.深入浅出索引(上)

简单来说,索引的出现就是为了提高数据查询效率,就像书的目录一样。 索引的常见模型 索引实现的方式有很多种,所以这里就引入了索引模型的概念,可以用于提高读写效率的数据结构很多,比较常...

scgaopan
49分钟前
5
0
Redis哨兵、复制、集群的设计原理,以及区别

谈到Redis服务器的高可用,如何保证备份的机器是原始服务器的完整备份呢?这时候就需要哨兵和复制。 **哨兵(Sentinel):**可以管理多个Redis服务器,它提供了监控,提醒以及自动的故障转移的...

Java阿七
59分钟前
5
0
浅析laravel路由执行原理

目前很多文章已经对Laravel的执行原理做了详细介绍,这里只是为了个人做一下简单记录 首先看入口 index.php 关键的执行函数就是 handle方法 ,但是前面的几个预处理函数,包括了整合框架的大...

冻结not
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部