1圈膏、問題

給定一個二叉樹與整數(shù)sum塔猾，找出所有從根節(jié)點到葉結(jié)點的路徑，這些路 徑上的節(jié)點值累加和為sum稽坤。

2丈甸、算法思路

• 從根節(jié)點深度遍歷二叉樹，先序遍歷時尿褪，將該節(jié)點值存儲至path棧中(vector實 現(xiàn))睦擂，使用 path_value累加節(jié)點值。
• 當(dāng)遍歷至葉結(jié)點時茫多，檢查path_value值是否為sum祈匙，若為sum忽刽，則將path push 進入result結(jié)果中天揖。
• 在后續(xù)遍歷時夺欲，將該節(jié)點值從path棧中彈出，path_value減去節(jié)點值今膊。

3些阅、代碼實現(xiàn)

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    vector< vector<int> > pathSum(TreeNode* root, int sum)
    {
        // 求以root為根結(jié)點的二叉樹中，
        // 哪些路徑（從根結(jié)點到葉節(jié)點）的總和為sum.

        vector< vector<int> > result;  // 保存最終結(jié)果
        vector<int> path;  // 單條路徑
        int path_value = 0;  // 路徑和
        preorder(root, sum, result, path, path_value);

        return result;
    }
private:
    void preorder(TreeNode* node, int sum, vector< vector<int> >& result,
            vector<int>& path, int& path_value)
    {
        if ( !node )
            return;

        // 針對于當(dāng)前節(jié)點斑唬，先加
        path_value += node->val;
        // 并保存到路徑path中
        path.push_back(node->val);

        // 判斷一下
        if (node -> left == NULL && node->right == NULL && path_value == sum)
        {
            result.push_back(path);
        }

        preorder(node->left, sum, result, path, path_value);
        preorder(node->right, sum, result, path, path_value);

        // 左右節(jié)點都處理完后
        path_value -= node->val;
        path.pop_back();
    }
};
int main()
{
    TreeNode a(5);
    TreeNode b(4);
    TreeNode c(8);
    TreeNode d(11);
    TreeNode e(13);
    TreeNode f(4);
    TreeNode g(7);
    TreeNode h(2);
    TreeNode i(5);
    TreeNode j(1);

    a.left = &b;
    a.right = &c;
    b.left = &d;
    d.left = &g;
    d.right = &h;
    c.left = &e;
    c.right = &f;
    f.left = &i;
    f.right = &j;

    Solution S;
    vector< vector<int> > result = S.pathSum(&a, 22);
    cout << "total path number: " << result.size() << endl;

    // 包裝一下打印結(jié)果
    cout << "[" << endl;
    for (int i = 0; i < result.size(); i++)
    {
        cout << "\t[";
        for (int j = 0; j < result[i].size(); j++)
        {
            if (j == (result[i].size() - 1))
                cout << result[i][j];
            else
                cout << result[i][j] << ",";
        }
        if (i == (result.size() - 1))
            cout << "]" << endl;
        else
            cout << "]," << endl;
    }
    cout << "]" << endl;
    return 0;
}