This approach involves recursively checking each node of the trees. You start at the roots and compare their values. If they are the same, you proceed to check their left and right subtrees. If at any point the checks fail (either structure or node values don't match), you conclude that the trees are not identical.
The time complexity of this approach is O(N), where N is the total number of nodes in the trees, since each node is visited once. The space complexity is O(H) for the recursion stack, where H is the height of the trees.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def isSameTree(p, q):
8 if not p and not q:
9 return True
10 if not p or not q:
11 return False
12 return (p.val == q.val) and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)The Python version of the solution defines a TreeNode class and implements the isSameTree function to recursively compare the trees starting from the root node, evaluating each node's value and subtree structure.
This approach involves using a stack to iteratively check whether two trees are identical. You use a stack to simulate the recursive process, always working on node pairs from both trees. For every processed pair, check for value equality, then push their children into the stack to process afterwards (with left and right children being compared correspondingly).
The time complexity remains O(N) since each node is processed exactly once. Space complexity could also be up to O(H) for the stack usage, being the tree's height.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def isSameTree(p, q):
8 stackP = [p]
9 stackQ = [q]
10 while stackP and stackQ:
11 nodeP = stackP.pop()
12 nodeQ = stackQ.pop()
13 if not nodeP and not nodeQ:
14 continue
15 if not nodeP or not nodeQ or nodeP.val != nodeQ.val:
16 return False
17 stackP.append(nodeP.right)
18 stackP.append(nodeP.left)
19 stackQ.append(nodeQ.right)
20 stackQ.append(nodeQ.left)
21 return not stackP and not stackQThis Python implementation uses lists as stacks to iteratively compare tree nodes. Both lists maintain pairs of nodes being checked for structure and value equality at this iteration.