查找所有路径和的算法的时间复杂度是多少？

Question

Path Sum给定一棵二叉树和一个和，找到所有从根到叶的路径，其中每个路径的和等于给定的和。例如： sum = 11。

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

答案是：

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

---

我个人认为，时间复杂度= O（2 ^ n），n是给定二叉树的节点。

---

谢谢Vikram Bhat和David Grayson，时间紧复杂度= O（nlogn），n是给定二进制文件中的节点数树。

• 算法一次检查每个节点，这会导致O（n）
• “ vector one_result（subList）;”每次都会将整个路径从subList复制到one_result，这会导致O（logn），因为高度为O（logn）。

最后，时间复杂度= O（n * logn）= O（nlogn）。

---

此解决方案的想法是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();
    }
};

Answer 1

尽管似乎时间复杂度为O(N)，但是如果您需要打印所有路径，则为O(N*logN)。假设u具有complete binary tree，则总路径将为N/2，并且每个路径将具有logN节点，因此在最坏的情况下总共为O(N*logN)。

Answer 2

您的算法看起来正确，并且复杂度应该为O（n），因为您的辅助函数将对每个节点运行一次，并且n是节点数。

Update：实际上，它应该是O（N * log（N）），因为每次运行辅助函数时，它可能会打印一个由O（log（N））节点组成的控制台路径，并且它将运行O（N）次。

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）。因为对于二叉树，只有一条路径可以到达任何叶节点，所以我们可以很容易地说，二叉树中的
root-to-leaf

路径总数不能超过叶数。我们知道二叉树中的叶子不能超过N / 2个，因此所有路径列表中的最大元素数将为O（N / 2）= O（N ）。现在，每个路径中都可以包含许多节点。对于平衡的二叉树（如上），每个叶节点将处于最大深度。我们知道平衡二叉树的深度（或高度）为O（logN），我们可以说每个路径最多可以有logN个节点。这意味着所有路径列表的总大小将为O（N * logN）。如果树不平衡，那么我们在最坏情况下的空间复杂度仍然相同。通过以上讨论，我们可以得出结论，我们算法的整体

空间复杂度

为O(N*logN)。也是从上述讨论开始，因为对于每个叶节点，在最坏的情况下，我们必须复制log(N)节点以存储其路径，因此算法的

时间复杂度

也将为O(N*logN)。