Practice/Snowflake/Leetcode 872. Leaf-Similar Trees

Leetcode 872. Leaf-Similar Trees

CodingMust

Problem

Given the roots of two binary trees, determine whether they have identical leaf value sequences. A leaf is defined as a node with no children. The leaf value sequence is the ordered list of all leaf node values when traversed from left to right.

Return true if and only if the two trees produce the same leaf value sequence when their leaves are read from left to right.

Requirements

1. Extract the leaf values from both trees in left-to-right order
2. Compare the two sequences for equality
3. Return true if the sequences match, false otherwise
4. Handle trees of different structures and sizes

Constraints

• The number of nodes in each tree is in the range [1, 200]
• Both trees will have at least one leaf node
• Node values are in the range [0, 200]
• Time complexity should be O(n + m) where n and m are the number of nodes in each tree
• Space complexity should be O(h₁ + h₂) where h₁ and h₂ are the heights of the trees

Examples

Example 1:

` Input: Tree1: 3 /
5 1 / \ /
6 2 9 8 /
7 4

Tree2: 3 /
5 1 / \
6 7 2 / \ /
4 9 8 null

Output: true Explanation: Both trees have the leaf sequence [6, 7, 4, 9, 8] when read from left to right. `

Example 2:

` Input: Tree1: 1 /
2 3

Tree2: 1 /
3 2

Output: false Explanation: Tree1 has leaf sequence [2, 3] while Tree2 has leaf sequence [3, 2]. `

Example 3:

` Input: Tree1: 1

Tree2: 1

Output: true Explanation: Both trees consist of a single leaf node with value 1. `