首页 > 代码库 > <LeetCode OJ> 100. Same Tree

<LeetCode OJ> 100. Same Tree

100. Same Tree

Total Accepted: 100129 Total Submissions: 236623 Difficulty: Easy

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,朴素的递归思想:

1)。函数返回值怎样构成原问题的解

明白函数意义,

推断以节点p和q为根的二叉树是否一样,获取当前以p和q为根的子树的真假情况

bool isSameTree(TreeNode* p, TreeNode* q){

    函数体.....

}

解的构成,

每个节点的左子树和右子树同一时候一样才干组合成原问题的解。原问题接收来自全部子问题的解。仅仅要有一个假就可以全部为假(与运算)


2)。递归的截止条件

截止条件就是能够得出结论的条件。

假设p和q两个节点是叶子,即都为NULL,能够觉得是一样的。return true

假设存在一个为叶子而还有一个不是叶子,显然当前两个子树已经不同,return false

假设都不是叶子,但节点的值不相等,最显然的不一样。return false


3)总是反复的递归过程

当2)中全部的条件都“躲过了”,即q和p的两个节点是同样的值。那就继续推断他们的左子树和右子树是否一样。

即,isSameTree(p->left,q->left)和isSameTree(p->right,q->right)


4)控制反复的逻辑

显然仅仅有两个子树都同样时,才干获取终于结果,否则即为假。

例如以下所看到的

return (isSameTree(p->left,q->left))&&(isSameTree(p->right,q->right));

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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


2,广度优先迭代遍历:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //思路首先:递归能做,显然迭代也能做,以下採用了广度优先遍历两棵树是否一样
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
      if(q==NULL && p ==NULL)  
        return true; 
      if(q == NULL && p!=NULL || q != NULL && p==NULL)    
            return false;
      //广度优先遍历两个子树是否一样  
      queue<TreeNode*> que1,que2;    
      TreeNode* curNode1=p;
      TreeNode* curNode2=q;      
      que1.push(curNode1);  
      que2.push(curNode2);
      while (!que1.empty()&&!que2.empty())    
      {      
         curNode1=que1.front();//出队首元素      
         que1.pop();//删除队首元素  
         curNode2=que2.front();//出队首元素      
         que2.pop();//删除队首元
         if(!(curNode1->val==curNode2->val))
            return false;
         if(curNode1->left!=NULL && curNode2->left!=NULL)    
         {   
            que1.push(curNode1->left);    
            que2.push(curNode2->left); 
         }
         
         if(curNode1->right!=NULL && curNode2->right!=NULL)    
         {     
             que1.push(curNode1->right);
             que2.push(curNode2->right); 
         }
         if(curNode1->left == NULL && curNode2->left!=NULL || curNode1->left != NULL && curNode2->left==NULL)    
            return false;
            
         if(curNode1->right == NULL && curNode2->right!=NULL || curNode1->right != NULL && curNode2->right==NULL)    
            return false;
      }  
      return true;  
    }
};




3,前序式深度优先搜索来做

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //思路首先:递归能做,显然迭代也能做。以下採用了前序式深度优先遍历两棵树是否一样
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
      if(q==NULL && p ==NULL)  
        return true; 
      if(q == NULL && p!=NULL || q != NULL && p==NULL)    
            return false;
      //前序式深度优先遍历两个子树是否一样  
      stack<TreeNode*> stk1,stk2;    
      TreeNode* curNode1=p;
      TreeNode* curNode2=q;      
      stk1.push(curNode1);  
      stk2.push(curNode2);
      while (!stk1.empty()&&!stk2.empty())    
      {      
         curNode1=stk1.top();//出队首元素      
         stk1.pop();//删除队首元素  
         curNode2=stk2.top();//出队首元素      
         stk2.pop();//删除队首元
         if(!(curNode1->val==curNode2->val))
            return false;
         if(curNode1->left!=NULL && curNode2->left!=NULL)    
         {   
            stk1.push(curNode1->left);    
            stk2.push(curNode2->left); 
         }
         
         if(curNode1->right!=NULL && curNode2->right!=NULL)    
         {     
             stk1.push(curNode1->right);
             stk2.push(curNode2->right); 
         }
         if(curNode1->left == NULL && curNode2->left!=NULL || curNode1->left != NULL && curNode2->left==NULL)    
            return false;
            
         if(curNode1->right == NULL && curNode2->right!=NULL || curNode1->right != NULL && curNode2->right==NULL)    
            return false;
      }  
      return true;  
    }
};




注:本博文为EbowTang原创,兴许可能继续更新本文。假设转载,请务必复制本条信息!

原文地址:http://blog.csdn.net/ebowtang/article/details/50507131

原作者博客:http://blog.csdn.net/ebowtang

本博客LeetCode题解索引:http://blog.csdn.net/ebowtang/article/details/50668895

&lt;LeetCode OJ&gt; 100. Same Tree