Same Tree
LeetCode #100 · Easy · Trees · C++ solution with worked-out approach and complexity analysis.
Approach
Recursive DFS
Compare two trees recursively by checking: 1. If both nodes are null, they are the same 2. If one is null and the other isn't, they are different 3. If values differ, they are different 4. Recursively check left and right subtrees
Time
O(min(m, n))
m and n are number of nodes in p and q
Space
O(min(m, n))
recursion stack depth
Problem description(from LeetCode)
Given the roots of two binary trees p and q, 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.
Examples
Example 1
- Input:
- p = [1,2,3], q = [1,2,3]
- Output:
- true
Example 2
- Input:
- p = [1,2], q = [1,null,2]
- Output:
- false
Example 3
- Input:
- p = [1,2,1], q = [1,1,2]
- Output:
- false
Constraints
- •The number of nodes in both trees is in the range [0, 100].
- •-10^4 <= Node.val <= 10^4
C++ Solution
solution.cpp
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right)
: val(x), left(left), right(right) {}
};
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};