(LeetCode OJ) Same Tree【100】

100. Same Tree

My SubmissionsQuestionTotal 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.

Subscribe to see which companies asked this question

Hide Tags Tree Depth-first Search

樸素的遞歸思想：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //思路首先：只要p和q都不為null且val相等就繼續判斷p的左子樹和q的左子樹以及p的右子樹和q的右子樹
 //如果出現某子樹存在而另一顆樹的相應子樹卻不存在，則返回false
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));  
    }
};