javascript - 打印二叉搜索树中最长路径的时间复杂度

Question

问题：给定一个二叉搜索树，打印出最长的路径。

方法：在每个级别存储可能的深度并过滤掉最长的一个。这个时间复杂度一定至少 O(n)是因为我们在某种意义上是在计算树的直径。但是，在每个级别，我们都调用reduce了一组可能的路径，以确定每个阶段的最长路径。我认为这会使每个阶段O(nk)的k数组长度变得复杂。空间复杂度为 O(n + k + j)，其中 n 是递归调用的深度，k 和 j 是数组。

问题：对时间复杂度的分析是否正确，第二，如何才能及时完成O(n)？

function printLongestPath(root = this.head, paths = [], finishedPaths = []) {

        if (!root) return;

        paths.push(root.data);

        if (!root.left && !root.right) {
            finishedPaths.push(paths);
            paths.pop();
            return;
        }

        this.printLongestPath(root.left, paths, finishedPaths);
        this.printLongestPath(root.right, paths, finishedPaths);

        // Pop once more once both paths have finished because it means we are in an intermediary step

        paths.pop();


        return finishedPaths.reduce((longest, current) => {
          return current.length > longest.length ? current : longest
        }, finishedPaths[0]);

    }

标签： javascriptsearchtreetime-complexitybinary-search-tree