一.题目:相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的

  

   

    

     

    
    

     

      输入:       1         1
     
    
   

    

     

    
    

     

                / \       / \
     
    
   

    

     

    
    

     
         2   3     2   3
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              [1,2,3],   [1,2,3]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      输出: true
     
    
  
 

  

   

    

     

    
    

     

      输入:      1          1
     
    
   

    

     

    
    

     

                /           \
     
    
   

    

     

    
    

     
         2             2
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              [1,2],     [1,null,2]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      输出: false
     
    
  
 

  

   

    

     

    
    

     

      输入:       1         1
     
    
   

    

     

    
    

     

                / \       / \
     
    
   

    

     

    
    

     
         2   1     1   2
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              [1,2,1],   [1,1,2]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      输出: false
     
    
  
 

二.算法思想

首先判断 p 和 q 是不是 NULL，然后判断它们的值是否相等。若以上判断通过，则递归对子结点做同样操作。

三.代码

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 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;
     
    
   

    

     

    
    

     
        //判断是否都为空
     
    
   

    

     

    
    

     
        if(p==NULL||q==NULL) return false;
     
    
   

    

     

    
    

     
        //若有一个为空
     
    
   

    

     

    
    

     
        if(p->val!=q->val) return false;
     
    
   

    

     

    
    

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

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/104385825