Back to Trees
Easy
Same Tree
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
Input:p = [1,2,3], q = [1,2,3]
Output:true
Input:p = [1,2], q = [1,null,2]
Output:false
Constraints
The number of nodes in both trees is in the range [0, 100].-10^4 <= Node.val <= 10^4
Approach
Use a recursive DFS to traverse both trees simultaneously. Base cases: If both nodes are null, they are the same. If only one node is null, or if their values differ, they are not the same. If they match, recursively check their left children and right children.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Where n is the minimum number of nodes between the two trees.
Solution.java
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { // Both are null if (p == null && q == null) return true; // One is null or values differ if (p == null || q == null || p.val != q.val) return false; // Recursively check left and right subtrees return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }}