Problem 872

Question statement

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. 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.

Solution

Main idea:

More binary trees. Just do a depth first search (recuse) for each tree, everytime you reach a leaf, add it to a leaf array. Compare if both arrays are the same in the end.

Code:

def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        
    def dfs(root,leaf):
        if not root:
            return
        if not root.left and not root.right:
            leaf.append(root.val)
            return
        dfs(root.left, leaf)
        dfs(root.right, leaf)
    
    leafset1 = []
    leafset2 = []
    dfs(root1,leafset1)
    dfs(root2,leafset2)
    return leafset1 == leafset2

Comments:

Time complexity: O(n) where n is the number of nodes.

The above code runs in 26ms beats 99.1% of users. It uses 17.48MB of memory, beating 8.04% of users.