二叉树中和为某一值的路径

题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int>>result;
    vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
        vector<int>data;
        treePath(root,data,expectNumber);
        return result;
    }
    //vector<int>data ,这里不能使用引用，否则添加进入vector的值不会pop掉
    void treePath(TreeNode* root, vector<int>data,int expectNumber) {
        if (root == NULL) {
            return;
        }
        //添加该结点的值
        data.push_back(root->val);


        treePath(root->left, data,expectNumber);
        treePath(root->right,data,expectNumber);

        if (root->left== NULL&&root->right==NULL) {
            getPathSum(data,expectNumber);
        }
    }
    void getPathSum(vector<int>data, int expectNumber) {
        int sum = 0;
        for (int i = 0; i <data.size(); i++)
        {
            sum += data[i];
        }
        if (sum == expectNumber) {
            result.push_back(data);
        }
    }
};

//调试

void connectNode(TreeNode *p1, TreeNode *p2, TreeNode *p3) {
    if (p1 == NULL) {
        cout << "input error" << endl;
    }
    p1->left = p2;
    p1->right = p3;
}

//测试
int main() {
    TreeNode *pNode1 = new TreeNode(10);
    TreeNode *pNode2 = new TreeNode(5);
    TreeNode *pNode3 = new TreeNode(12);
    TreeNode *pNode4 = new TreeNode(4);
    TreeNode *pNode5 = new TreeNode(7);

    connectNode(pNode1,pNode2,pNode3);
    connectNode(pNode2,pNode4,pNode5);
    Solution s;
    vector<vector<int>>result = s.FindPath(pNode1,22);

    system("pause");

}