すべてのパス合計を見つけるためのこのアルゴリズムの時間計算量はどれくらいですか？

パスの合計
バイナリツリーと合計が与えられた場合、各パスの合計が指定された合計に等しいすべてのルートからリーフへのパスを見つけます。
例： sum = 11。

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

答えは：

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

個人的には、時間計算量= O（2 ^ n）、nは与えられた二分木のノードの数だと思います。

---

ありがとう ビクラムBhatさん と デビッド・グレイソン 、タイトな時間の複雑さ= O（nlogn）で、nは与えられたバイナリツリー内のノード数です。

• アルゴリズムは各ノードを1回チェックします。これにより、O（n）が発生します。
• "vector one_result（subList）;" 高さがO（logn）であるため、パス全体がsubListからone_resultに毎回コピーされ、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();
    }
};