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

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();
    }
};

Answer 1

虽然看起来时间复杂度是O(N)，但是如果你需要打印所有路径那么它是O(N*logN)。假设你有一棵完全二叉树，那么总路径将为N/2，每条路径都有logN个节点，所以总共有O(N*logN) 在最坏的情况下。