Leaf Similar Trees

This problem can be easily solved using recursive way.

class Solution {
    fun leafSimilar(root1: TreeNode?, root2: TreeNode?): Boolean {
        tailrec fun findLeaves(node: TreeNode?, collector: MutableList<TreeNode>){
            if(node == null) return
            
            if(node?.left == null && node?.right == null){
                collector.add(node!!)
                return
            }
            
            findLeaves(node?.left, collector)
            findLeaves(node?.right, collector)
        }
        
        var seq1 = mutableListOf<TreeNode>()
        var seq2 = mutableListOf<TreeNode>()
        
        findLeaves(root1, seq1)
        findLeaves(root2, seq2)
        
        return seq1.filterIndexed {index, i -> i.`val` != seq2[index].`val`}.isEmpty()
    }
}

The idea is to go through each of the nodes recursively and if the node’s left and right children are both null, then the node is a leaf. We then use a collector to collect these nodes.

After we collected all the leaves for both trees, we compare them one by one to verify if their contents are both equal.

Runtime: 140 ms, faster than 94.44% of Kotlin online submissions for Leaf-Similar Trees.
Memory Usage: 32 MB, less than 100.00% of Kotlin online submissions for Leaf-Similar Trees.
comments powered by Disqus