这个算法寻找所有路径总和的时间复杂度是多少？

Question

Path Sum
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example: sum = 11.

    5 
   / \ 
  4   8
 /   / \ 
2  -2   1 

The answer is :

[
  [5, 4, 2], 
  [5, 8, -2]
]

---

Personally I think, the time complexity = O(2^n), n is the number of nodes of the given binary tree.

---

Thank you Vikram Bhat and David Grayson, the tight time complexity = O(nlogn), n is the number of nodes in the given binary tree.

• Algorithm checks each node once, which causes O(n)
• "vector one_result(subList);" will copy entire path from subList to one_result, each time, which causes O(logn), because the height is O(logn).
  

So finally, the time complexity = O(n * logn) =O(nlogn).

---

The idea of this solution is DFS[C++].

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int>> list;

        // Input validation.
        if (root == NULL) return list;

        vector<int> subList;
        int tmp_sum = 0;

        helper(root, sum, tmp_sum, list, subList);

        return list;
    }

    void helper(TreeNode *root, int sum, int tmp_sum, 
                vector<vector<int>> &list, vector<int> &subList) {

        // Base case.
        if (root == NULL) return;
        if (root->left == NULL && root->right == NULL) {
            // Have a try.
            tmp_sum += root->val;
            subList.push_back(root->val);

            if (tmp_sum == sum) {
                vector<int> one_result(subList);
                list.push_back(one_result);
            }

            // Roll back.
            tmp_sum -= root->val;
            subList.pop_back();

            return;
        }

        // Have a try.
        tmp_sum += root->val;
        subList.push_back(root->val);

        // Do recursion.
        helper(root->left, sum, tmp_sum, list, subList);
        helper(root->right, sum, tmp_sum, list, subList);

        // Roll back.
        tmp_sum -= root->val;
        subList.pop_back();
    }
};

- Zhaonan

---

这个问题似乎不适合，因为它涉及算法理论而非编程。 - Kerrek SB

很抱歉，但我认为算法理论是编程的一部分。 - Zhaonan

@KerrekSB：你知道我们在这里有一个算法标签的原因吗？ - László Papp

Answer 1

尽管时间复杂度看起来是 O(N)，但如果您需要打印所有路径，则为 O(N*logN)。假设您有一棵完全二叉树，则总路径数将为N/2，每条路径将有logN个节点，因此最坏情况下总共需要O(N*logN)。

- Vikram Bhat

---

是的，谢谢Vikram Bhat，你提醒我有“vector<int> one_result(subList);”，它将从subList复制O(logN)个节点到one_result中，因此时间复杂度为O(NlogN)。非常感谢。正在编辑我的帖子。 - Zhaonan

Answer 2

你的算法看起来是正确的，复杂度应该是O(n)，因为你的辅助函数会为每个节点运行一次，n是节点数。

更新：实际上，它将是O(N*log(N))，因为每次辅助函数运行时，它可能会将由O(log(N))个节点组成的路径打印到控制台，并且它将运行O(N)次。

- David Grayson

---

嗨，David，我认为时间复杂度应该大于O(n)，因为在DFS中存在回溯，每个节点可能会被检查多次，但我真的不确定，所以在这里发帖问问题。但是非常感谢你的帮助。 - Zhaonan

@DavidGrayson 这是错误的。请考虑完全二叉树。 - Vikram Bhat

哦，是的，如果有很多路径，实际打印可能会比O(N)更慢。正在编辑我的答案。 - David Grayson

嗨，@DavidGrayson，你能帮我解决这个问题吗？非常感谢： “http://stackoverflow.com/questions/25234796/whats-time-complexity-of-this-algorithm-for-breaking-words-dynamic-programmin” - Zhaonan

Answer 3

TIME COMPLEXITY

算法的时间复杂度为O(N^2)，其中'N'是树中节点的总数。这是因为我们遍历每个节点一次（需要O（N）的时间），并且对于每个叶节点，我们可能需要存储其路径，这将需要O（N）的时间。

从下面的空间复杂性讨论中，我们可以计算出一个更紧密的时间复杂度为O(NlogN)。

SPACE COMPLEXITY

如果忽略所有路径列表所需的空间，该算法的空间复杂度在最坏情况下为O(N)。这个空间将用于存储递归栈。当给定树是一个链表（即每个节点只有一个子节点）时，最坏情况会发生。

如何估计所有路径列表使用的空间？以以下平衡树为例：

          1
      /      \
     2        3
   /   \    /   \
  4     5  6     7

这里有七个节点（即N = 7）。由于对于二叉树，到达任何一个叶子节点只存在一条路径，因此我们可以轻易地说，在二叉树中根到叶子节点的路径总数不能超过叶子节点数量。我们知道在二叉树中不能有超过N/2个叶子节点，因此所有路径列表中元素的最大数量将为O(N/2) = O(N)。现在，每个这样的路径中可能有许多节点。对于平衡的二叉树（如上文所述），每个叶子节点将位于最大深度处。由于我们知道平衡的二叉树的深度（或高度）是O(logN)，因此我们可以说，最多，每个路径可以具有logN个节点。这意味着所有路径列表的总大小将为O(N*logN)。如果树不平衡，我们仍将拥有相同的最坏空间复杂度。

从上面的讨论中，我们可以得出结论，我们算法的总体空间复杂度是O(N*logN)。

此外，从以上讨论中，由于对于每个叶子节点，在最坏情况下，我们必须复制log(N)个节点来存储其路径，因此我们算法的时间复杂度也将是O(N*logN)。

- tausif

---

这是educative.io的《Grokking the Coding Interview》中关于空间复杂度的答案。关于不平衡树具有相同空间复杂度的部分并不直观，需要解释。我可以拿7个节点创建一个不平衡的树，其中结果列表所需的空间将比它的平衡对应物更多。 - itsSLO

Answer 4

最坏情况下的时间复杂度不是O(nlogn)，而是O(n^2)。

• to visit every node, we need O(n) time

• to generate all paths, we have to add the nodes to the path for every valid path.
  So the time taken is sum of len(path). To estimate an upper bound of the sum: the number of paths is bounded by n, the length of path is also bounded by n, so O(n^2) is an upper bound. Both worst case can be reached at the same time if the top half of the tree is a linear tree, and the bottom half is a complete binary tree, like this:

  1
   1
    1
     1
      1
    1   1
   1 1 1 1
  

路径数量为n/4，每条路径的长度约为n/2 + log(n/2) ~ n/2。

- ssynhtn