题目描述(简单难度)

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
  7. 最差情况例子
  8. 1
  9. \
  10. 2
  11. \
  12. 3
  13. \
  14. 4

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

windliang wechat

添加好友一起进步~

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

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