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

Question

路径总和
给定一个二叉树和一个总和，找出所有根到叶的路径，其中每个路径的总和等于给定的总和。
例如：总和 = 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)
• “矢量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). 假设你有一个完整的二叉树，那么总路径将是，N/2并且每条路径在最坏的情况下将有logN节点总数O(N*logN)。