Why it works
- Two trees are the same exactly when their roots are equal, their left subtrees are the same and their right subtrees are the same, so isSame answers for a pair of nodes from the answers for their pairs of children.
- An empty child has to meet an empty child: here every value matches, and only the pair (4, none) under 6 shows that the shapes differ.
- The first false goes straight back up through every call, so the rest of both trees is never compared.
Complexity
Time O(n), where n is the size of the smaller tree: each pair of places is compared at most once. Memory O(h), where h is its height: the call stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗