872. Leaf-Similar Trees

Leaf-Similar Trees

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

Approach) Recursion

const leafSequence = root => {
    const res = []
    if (root)
        if (!root.left && !root.right) 
            res.push(root.val)
        else {
            res.push(...leafSequence(root.left))
            res.push(...leafSequence(root.right))
        }
    return res
}

Approach) Stack

const leafSequence = root => {
    const res = []
    const stack = [root] 
    while (stack.length) {
        const root = stack.pop()
        if (root)
            if (!root.left && !root.right)
                res.push(root.val)
            else {
                stack.push(root.left)
                stack.push(root.right)
            }
    }
    return res
}

Approach) Generators

const leafSequence = root => {
    const gen = function*(root) {
        if (root)
            if (!root.left && !root.right) 
                yield root.val
            else {
                yield* leafSequence(root.left)
                yield* leafSequence(root.right)
            }
    }
    return [...gen(root)]
}

Approach) Without Generators

const leafSequence = function*(root) {
    if (root)
        if (!root.left && !root.right) 
            yield root.val
        else {
            yield* leafSequence(root.left)
            yield* leafSequence(root.right)
        }
}

const leafSimilar = (root1, root2) => {
    let leaves1 = leafSequence(root1)
    for (let x of leafSequence(root2))
        if (x !== leaves1.next().value)
            return false
    return leaves1.next().done
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 872. Leaf-Similar Trees

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!