FXTi's blog
0%

same-tree

Posted on Edited on

Same Tree – LeetCode 100

Problem

Description

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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 != nullptr && q != nullptr){
            if(p->val == q->val)
                return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
            else 
                return false;
        } else if (p == nullptr && q == nullptr) return true;
            else {return false;}
    }
};

思路

通过DFS递归不断分解树进入左枝和右枝，时间复杂度$O(n)$，$n$为节点数，空间复杂度$O(n)$。
耗时$3$ ms，排名$49.70\%$

Better

思路

还有BFS的非递归解，使用FIFO的Queue来实现，性能优势可能仅在于递归所带来的函数调用开销，时间复杂度$O(n)$，$n$为节点数，空间复杂度$O(n)$。
耗时$3$ ms，排名$49.70\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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 && !q) return true;
        if((p && !q) || (!p && q)) return false; //either one is NULL
        queue<TreeNode *> quep, queq;
        quep.push(p);
        queq.push(q);
        TreeNode *pfront, *qfront;
        while(!quep.empty() && !queq.empty()){
            pfront = quep.front(); quep.pop();
            qfront = queq.front(); queq.pop();
            if(pfront->val != qfront->val) return false;
            if((!pfront->left && qfront->left) || (pfront->left && !qfront->left)) return false;
            if(pfront->left != qfront->left){
                quep.push(pfront->left);
                queq.push(qfront->left);
            }
            if((!pfront->right && qfront->right) || (pfront->right && !qfront->right)) return false;
            if(pfront->right != qfront->right){
                quep.push(qfront->right);
                queq.push(pfront->right);
            }
        }
        //return quep.size() == queq.size();
        return true;
    }
};