100. Same Tree

阅读量：4221 次

发布时间：2019-05-26

本文共 2968 字，大约阅读时间需要 9 分钟。

判断两课树是否是相等的树，提示tags有两种：tree和bfs。那联想到递归和BFS算法了。

题目描述:

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.

给出两棵二叉树，写一个函数判断它们是否相等。两棵二叉树在结构相等的时候还要判断节点的值是否相等。

1.递归：

bool isSameTree(TreeNode* p, TreeNode* q) {        if(p == NULL && q == NULL){
  return true; }        if(p == NULL && q != NULL){
  return false;}        if(p != NULL && q == NULL){
  return false;}        else{            if(p->val != q->val){                return false;            }            else{                return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);            }         }     }

分析下几种情况：

1.p和q都为NULL时返回true

2.p和q一个为NULL而另外一个不为NULL，在结构上就不等，返回false

3.除此之外，就是都存在左右节点，那就应该比较它们的val了，如果不等，就可以直接返回false；如果相等，继续判断它们的左右节点，递归下去

最后的答案必须是左右子树都相等，才返回true，&&上它们

注:其实真正的返回值是p==NULL&&q==NULL返回的true，因为两棵树相等的话，一路递归下去，都没有返回false，直到最后的p==NULL&&q==NULL，这时的p和q代表最深的叶子节点

python代码：

class Solution(object):    def isSameTree(self, p, q):        if p == None and q == None:            return True        if p is not None and q is None:            return False        if p is None and q is not None:            return False        else:            if p.val != q.val:                return False            else:                return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

注：python中使用and表示&&，or表示||。

2.BFS

广度优先遍历

这里的思路是：

1.构造两个队列了l1和l2，用这两个队列同步搜索树的所有节点并进队，每一次进队看树的这个位置有几个节点，有左右就先进左再进右，只有一个就进那一个（bfs能把所有的节点都扫描到并且进队列）

2.之后是比较队头元素，先将队头元素拷贝一份，直接直接删除，如果拷贝的队头元素的val不相等，直接返回false；否则继续下一次循环，可见下一次循环又是新的队头元素

这样比较下去直到两棵树都空了，还没有返回false，说明两个树是完全相等的，返回true

很明显看的出来这是树的层次遍历，从上到下，从左到右，也就是广度

class Solution {public:    bool isSameTree(TreeNode* p, TreeNode* q) {       if(p == NULL && q == NULL){
  return true;}       if((p == NULL && q != NULL) || (p != NULL && q == NULL)){
  return false;}       queue
   
     l1;       queue
    
      l2;       l1.push(p);  //只是压了个头部进去，根节点       l2.push(q);       TreeNode* node1 = p;       TreeNode* node2 = q;       while(!l1.empty() && !l2.empty()){           node1 = l1.front();           l1.pop();           node2 = l2.front();           l2.pop();           if(node1->val != node2->val){               return false;           }           if(node1->left != NULL && node2->left != NULL){               l1.push(node1->left);               l2.push(node2->left);  //node1,2指针偏移           }           if(node1->right != NULL && node2->right != NULL){               l1.push(node1->right);               l2.push(node2->right);  //node1,2指针偏移           }           //如果树的结构不同，那直接返回false           if(node1->left == NULL && node2->left != NULL ||node1->left != NULL && node2->left == NULL){               return false;           }           if(node1->right == NULL && node2->right != NULL || node1->right != NULL && node2->right == NULL){               return false;           }         }         return true;      }};

转载地址：http://femmi.baihongyu.com/

你可能感兴趣的文章