872.叶子相似的树

题目#872.叶子相似的树

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

题目分析

这题可以看做有了条件的深度优先搜索，条件就是遍历到的节点是叶子节点。分别将两个树的叶子节点保存在两个数组然后比较即可。

代码如下

class Solution {
    fun leafSimilar(root1: TreeNode?, root2: TreeNode?): Boolean {
        return fillArr(root1, ArrayList()) == fillArr(root2, ArrayList())
    }

    private fun fillArr(root: TreeNode?, temp: ArrayList<Int>): ArrayList<Int> {
        if (root == null) return temp
        if (root.left == null && root.right == null) {
            temp.add(root.`val`)
            return temp
        }
        fillArr(root.left, temp)
        fillArr(root.right, temp)
        return temp
    }
}

代码分析

值得注意的是，我们可以在kotlin中使用 == 来判断两个数组是否有相同的元素。 本题中的==相当于调用了java.util.ArrayList#equals方法。