Sponsored
Sponsored
This approach involves using a recursive depth-first search (DFS) to traverse each binary tree and collect the leaf node values by diving into each sub-tree starting from the root node. We store the values of all leaf nodes from left to right in a list. After extracting the sequences from both trees, we compare these sequences to determine if the trees are leaf-similar.
Time Complexity: O(N) where N is the number of nodes in the tree, as we need to visit each node.
Space Complexity: O(H) where H is the height of the tree, due to the recursive stack.
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
7class Solution:
8 def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
9 def dfs(node):
10 if not node:
11 return []
12 if not node.left and not node.right:
13 return [node.val]
14 return dfs(node.left) + dfs(node.right)
15
16 return dfs(root1) == dfs(root2)We define a nested function dfs inside our main function to recursively traverse the binary tree. The dfs function returns a list of leaf node values by first checking if a node is null (in which case it returns an empty list), then it checks if the node is a leaf node (no left and right children), and if so, it returns a list containing the node's value. Otherwise, it recursively calls itself on the left and right children and concatenates their results. Lastly, we compare the two leaf sequences to decide if the trees are leaf-similar.
This method employs an iterative version of depth-first search utilizing a stack to collect leaves of the tree. By substituting recursion with a stack, we manually handle tree traversal, but the core logic remains similar: traverse each tree, collect leaves, and compare leaf sequences.
Time Complexity: O(N), with N as the number of nodes in the tree, because every node is visited.
Space Complexity: O(H), where H is the height of the tree. This space is used by the stack during DFS traversal.
1function TreeNode(val, left, right)
This JavaScript implementation employs a stack in lieu of recursion, traversing the tree iteratively while storing leaf values in an array leaves. By iterating over the stack, we manage the state of traversal explicitly. Comparison between the leaf sequences relies on checking equality between the serialized JSON strings for simplicity.