100. Same Tree
1. 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.
2. Example
Example 1:
Input: [1,2,3], [1,2,3]
Output: true
Example 2:
Input: [1,2], [1,null,2]
Output: false
Example 3:
Input: [1,2,1], [1,1,2]
Output: false
3. Solutions
My Accepted Solution
n is min number of nodes in i_treeP and i_treeQ
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if (p == nullptr && q == nullptr) {
return true;
} else if (p != nullptr && q != nullptr && p->val == q->val) {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
} else {
return false;
}
}
};