39. Same Tree
You are given the roots p and q of two binary trees. Return true if they are identical: the same shape, with equal values in every matching position. Otherwise return false.
Two empty trees count as identical.
Input: p = [1,2,3], q = [1,2,3] Output: true
Input: p = [1,2], q = [1,null,2] Output: false
Explanation: In p the 2 is a left child, in q it is a right child. The values match but the shapes do not.
Input: p = [1,2,1], q = [1,1,2] Output: false
Constraints
- Each tree has between
0and100nodes -10^4 <= Node.val <= 10^4
💡 Hint 1
Compare the two roots first. What must be true about them before looking deeper?
💡 Hint 2
If both nodes are null the trees match here; if exactly one is null they do not. Otherwise the values must be equal and both pairs of children must match recursively.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Walk both trees in lockstep. At each pair of positions: if both nodes are null this branch matches; if only one is null, or the values differ, the trees differ. Otherwise recurse on the two left children and the two right children, and require both to match. The && short-circuits, so the walk stops at the first difference.
function isSameTree(p, q) {
if (!p || !q) return p === q;
return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) return p == q;
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}No submissions yet. Press Submit to run your code against every test.
/**
* Definition for a binary tree node (provided):
* function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
*
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
function isSameTree(p, q) {
}Run your code to see results here.