872. Leaf-Similar Trees

Leetcode link

题目简介

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */

题目给我们两个二叉树的根节点

要求我们求出两棵树是否是叶子节点相似的

叶子节点相似的意思是，从左到右遍历叶子节点其元素与顺序一致

解题思路

我们分别准备两个数组 arr1 与 arr2 来保存我们遍历到的叶子节点元素

接下来我们用 dfs 进行树的前序遍历，在遍历过程中把遇到的所有叶子节点推进数组中

最后对比两个数组即可

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function (root1, root2) {
    const arr1 = []
    const arr2 = []

    const dfs = (node, arr) => {
        if (!node) {
            return
        }

        if (!node.left && !node.right) {
            arr.push(node.val)
        }
        dfs(node.left, arr)
        dfs(node.right, arr)
    }

    dfs(root1, arr1)
    dfs(root2, arr2)

    if (arr1.length !== arr2.length) {
        return false
    }

    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] !== arr2[i]) {
            return false
        }
    }
    return true
};

复杂度分析

时间

假设 N = root1.length, M = root2.length

我们对两棵树都进行了 dfs，需要遍历所有的树节点，时间分别是 O(N)、O(M)

此外我们进行了数组的比较，但是数组元素小于 N 或 M（最差的情况就是树节点的一半），所以不是主导

最后的时间复杂度就是 O(N + M)

空间

我们使用了两个数组 arr1，arr2 这两个数组最坏的情况会有树节点的一半数量的元素，所以分别是 O(N)、O(M)

此外我们还用了 DFS 遍历了两棵树，遍历的空间取决于树的高度：

• 最好的情况：O(logN)、O(logM)
• 最差的情况（单边树）：O(N)、O(M)

最后整体的空间复杂度是 O(N + M)