1. 首页
  2. Leetcode经典148题

leetcode-100-Same-Tree

题目描述(简单难度)

leetcode-100-Same-Tree

判断两个二叉树是否相同。

解法一

这道题就很简单了,只要把两个树同时遍历一下,遍历过程中判断数值是否相等或者同时为 null 即可。而遍历的方法,当然可以选择 DFS 里的先序遍历,中序遍历,后序遍历,或者 BFS。

当然实现的话,可以用递归,用栈,或者中序遍历提到的 Morris。也可以参照 “> 94 题 ,对二叉树的遍历讨论了很多。

这里的话,由于最近几题对中序遍历用的多,所以就直接用中序遍历了。

public boolean isSameTree(TreeNode p, TreeNode q) {
    return inorderTraversal(p,q);
}
private boolean inorderTraversal(TreeNode p, TreeNode q) {
    if(p==null&&q==null){
        return true;
    }else if(p==null || q==null){
        return false;
    }
    //考虑左子树是否符合
    if(!inorderTraversal(p.left,q.left)){
        return false;
    }
    //考虑当前节点是否符合
    if(p.val!=q.val){
        return false;
    }
    //考虑右子树是否符合
    if(!inorderTraversal(p.right,q.right)){
        return false;
    }
    return true;
}

时间复杂度:O(N)。对每个节点进行了访问。

空间复杂度:O(h),h 是树的高度,也就是压栈所耗费的空间。当然 h 最小为 log(N),最大就等于 N。

最好情况例子
      1
    /  \
   2    3
  / \  / \
 4  5 6   7

最差情况例子
     1
      \
       2
        \
         3
          \
           4

这道题比较简单,本质上考察的就是二叉树的遍历。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetcode-100-Same-Tree

链接:https://www.javajike.com/article/3237.html

« leetcode100斩回顾
leetcode-101-Symmetric-Tree»

相关推荐

QR code