Same Tree
EasyThe problem
Given two binary trees p and q, return true if they have exactly the same shape and every matching node holds the same value. Otherwise return false.
- Example 1Input: p = [1, 2, 3], q = [1, 2, 3]Output: true
- Example 2Input: p = [1, 2], q = [1, null, 2]Output: false
Both have the nodes 1 and 2, but 2 is a left child in p and a right child in q.
Limits
- 0 ≤ number of nodes in each tree ≤ 100
- Two empty trees count as the same
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Two trees are the same if the roots match and the children trees match.
The idea
Both nil → true; one nil → false; values differ → false; else recurse on left pair and right pair.
Target: O(n) time
Go function shape
func isSameTree(p *TreeNode, q *TreeNode) boolReference solution
Tested with go test. Try it yourself first, then compare.
// IsSameTree: two trees are the same when the roots match and both pairs of subtrees match.
func IsSameTree(p, q *TreeNode) bool {
if p == nil || q == nil {
return p == q // both nil is a match; one nil is not
}
return p.Val == q.Val && IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right)
}