---
###### tags: `Leetcode`
---
# Leetcode 872. Leaf-Similar Trees

[link](https://leetcode.com/problems/leaf-similar-trees/description/)

---

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.


For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

#### Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

#### Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

#### Constraints:

- The number of nodes in each tree will be in the range [1, 200].
- Both of the given trees will have values in the range [0, 200].

---

BFS

I use the helper function to traverse each tree recursively and retrieve the sequence of leaf nodes of each tree. Create a list to store the leaf nodes and then compare the two lists. Return True if they are the same.

#### Solution 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def helper(lst, root):
            if root.left is None and root.right is None:
                lst.append(root.val)
            if root.left is not None:
                helper(lst, root.left)
            if root.right is not None:
                helper(lst, root.right)

            return lst
                
        return helper([], root1) == helper([], root2)
        

O(T): O(V+E)
O(S): O(W)

---

DFS

We can maintain a stack and start with the root node. For each node, we check if it is a leaf node, and if so, we append its value to the list. Otherwise, we add the left and right child nodes to the stack (if they exist). We continue this process until the stack is empty.

#### Solution 2

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def get_leaf_nodes(root):
            stack = [root]
            leaf_nodes = []
            while stack:
                node = stack.pop()
                if not node.left and not node.right:
                    leaf_nodes.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return leaf_nodes

        return get_leaf_nodes(root1) == get_leaf_nodes(root2)
        

O(T): O(n)
O(S): O(h)