Introduction

In this blog post, we will explore how to solve the LeetCode problem "872" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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].

Explanation

Here's a solution to determine if two binary trees are leaf-similar, following the requested format:

• High-level Approach:

  • Perform a Depth-First Search (DFS) on each tree to extract their leaf value sequences.
  • Compare the two generated leaf value sequences. If they are identical, the trees are leaf-similar.
  • Return True if the sequences match, False otherwise.

• Complexity:

  • Runtime: O(N + M), where N and M are the number of nodes in root1 and root2 respectively.
  • Storage: O(H1 + H2), where H1 and H2 are the heights of root1 and root2 respectively, due to the recursion stack in DFS. In the worst case (skewed trees), this can be O(N + M). Additionally, O(L1 + L2) space is used to store the leaf value sequences, where L1 and L2 are the number of leaves in each tree.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def leafSimilar(root1, root2):
    """
    Determines if two binary trees are leaf-similar.

    Args:
        root1: The root node of the first binary tree.
        root2: The root node of the second binary tree.

    Returns:
        True if the trees are leaf-similar, False otherwise.
    """

    def get_leaf_sequence(root):
        """
        Performs a Depth-First Search (DFS) to extract the leaf value sequence of a tree.

        Args:
            root: The root node of the binary tree.

        Returns:
            A list representing the leaf value sequence.
        """
        leaf_sequence = []

        def dfs(node):
            if not node:
                return

            if not node.left and not node.right:
                leaf_sequence.append(node.val)
                return

            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return leaf_sequence

    leaf_sequence1 = get_leaf_sequence(root1)
    leaf_sequence2 = get_leaf_sequence(root2)

    return leaf_sequence1 == leaf_sequence2