题目描述（简单难度）

100. Same Tree - 图1

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

解法一

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

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

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

  1. public boolean isSameTree(TreeNode p, TreeNode q) {
  2.     return inorderTraversal(p,q);
  3. }
  4. private boolean inorderTraversal(TreeNode p, TreeNode q) {
  5.     if(p==null&&q==null){
  6.         return true;
  7.     }else if(p==null || q==null){
  8.         return false;
  9.     }
  10.     //考虑左子树是否符合
  11.     if(!inorderTraversal(p.left,q.left)){
  12.         return false;
  13.     }
  14.     //考虑当前节点是否符合
  15.     if(p.val!=q.val){
  16.         return false;
  17.     }
  18.     //考虑右子树是否符合
  19.     if(!inorderTraversal(p.right,q.right)){
  20.         return false;
  21.     }
  22.     return true;
  23. }

时间复杂度：O（N）。对每个节点进行了访问。

空间复杂度：O（h），h 是树的高度，也就是压栈所耗费的空间。当然 h 最小为 log（N），最大就等于 N。

  1. 最好情况例子
  2.       1
  3.     /  \
  4.    2    3
  5.   / \  / \
  6.  4  5 6   7
  8. 最差情况例子
  9.      1
  10.       \
  11.        2
  12.         \
  13.          3
  14.           \
  15.            4

总

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

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情