最大总和根到叶二叉树的时间复杂度

Question

int ma = INT_MIN;
int parent[1000];

int findMaxPath(struct node * ptr) {
    if (ptr == NULL) return 0;
    if (ptr->left == NULL && ptr->right == NULL) {
        // means leaf node
        int sum = ptr->data;
        int temp = ptr->data;
        while (parent[temp] != -1) {
            sum = sum + parent[temp];
            temp = parent[temp];
        }
        if (sum > ma)
            ma = sum;
    }
    else{
        if (ptr->left != NULL)
            parent[ptr->left->data] = ptr->data;
        if (ptr->right != NULL)
            parent[ptr->right->data] = ptr->data;
        findMaxPath(ptr->left);
        findMaxPath(ptr->right);
    }
}

方法 - 一旦我确定了叶节点，我就使用父数组回溯到根节点并对所有值求和，如果这个求和值大于最大值，则更新最大值。我不确定这段代码的时间复杂度你能帮我看看这段代码的时间复杂度吗？

Answer 1

平衡树的复杂度是O(N*log(N))，因为一半的节点都是叶子，遍历到根需要log(N)。如果树不平衡，你的速度可能会降低到 O(N²).

您可以通过将总和存储在您遇到的每个节点中来修复您的方法，在这种情况下，时间复杂度将为 O(n)，因为您永远不会重新计算您拥有的根到节点总和计算一次。

另一种使此线性化的方法是从根开始运行 a BFS or DFS，然后计算每个顶点的总和。 DFS实现很简单：

int max_sum(node *n, int partial) {
    if (n == NULL) {
        return partial;
    }
    int my_sum = partial + n->value;
    return max(max_sum(n->left, my_sum), max_sum(n->right, my_sum));
}

// Running the code:
int maxSumInTree = max_sum(root, 0);

Answer 2

时间复杂度根据树的结构变化很大。

对于平衡树，从根到叶的每条路径至多为 O(logn)，并且不超过 n 个叶子（显然），所以 O(nlogn)
对于单链单叶树 - 它是 O(n)，因为你最多做一次。
对于每棵右子树的高度恰好为 1 的树，它是 O(n^2)，因为你对正在增加的路径的长度求和：1 + 2 + ... + n/2，它在 O(n^2) 中来自算术级数的总和。

算法的最坏情况是O(n^2)，因为叶子的数量不超过n，并且每个深度不超过n - 给出了 O(n^2) 的上限，从例子中我们看到这个界限很紧。

算法的平均情况是O(nlogn)，因为tree's average height is logarithmic.

时间O(n)，时间O(h)space的改进方案可以是DFS，其中存储和计算局部和，当遇到"better" 解决方案，只需编辑指向 "better" 解决方案所需的指针。

最大总和根到叶二叉树的时间复杂度

Max sum root to leaf binary tree time complexity

c++

algorithm

tree

recursion

binary-tree