Same Tree
Examples
Example 1:
Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Example 2:
Input: p = [4, 7], q = [4, null, 7]
Output: false
Example 3:
Input: p = [1, 2, 3], q = [1, 3, 2]
Output: false
Example 1:
Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Example 2:
Input: p = [4, 7], q = [4, null, 7]
Output: false
Example 3:
Input: p = [1, 2, 3], q = [1, 3, 2]
Output: false
Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.\n\nTwo binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.
0 <= The number of nodes in both trees <= 100-100 <= Node.val <= 100Compare the two trees with DFS. If both nodes are null, they match; if only one is null or values differ, they do not. Otherwise, recursively compare left and right subtrees. This handles empty trees and differing shapes.
Two trees are identical iff their roots have equal values and their left and right subtrees are identical. The recursive check enforces this definition at every node, so it returns true exactly for equivalent trees.
O(n)O(h)class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)