題目描述 [二叉樹中和為某一值的路徑]

輸入一顆二叉樹的跟節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中，數(shù)組長(zhǎng)度大的數(shù)組靠前)

解題思路

http://www.cnblogs.com/edisonchou/p/4787736.html

• 當(dāng)用前序遍歷的方式訪問到某一結(jié)點(diǎn)時(shí)，我們把該結(jié)點(diǎn)添加到路徑上，并累加該結(jié)點(diǎn)的值。
• 如果該結(jié)點(diǎn)為葉結(jié)點(diǎn)并且路徑中結(jié)點(diǎn)值的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它添加到結(jié)果中去。如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問它的子結(jié)點(diǎn)。
• 當(dāng)前結(jié)點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動(dòng)回到它的父結(jié)點(diǎn)。這里要注意的是：在函數(shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是從根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。

代碼

class Solution {
public:
    void FindPath(vector<vector<int> > &res, vector<int> &temp,TreeNode* root,int expectNumber, int val) {
        temp.push_back(root->val);
        val += root->val;

        if(!root->left && !root->right && val==expectNumber){
            res.push_back(temp);
        }
        if(root->left) FindPath(res, temp, root->left,expectNumber,val);        
        if(root->right) FindPath(res, temp, root->right,expectNumber,val);
        temp.pop_back();
        val -= root->val;
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > res;
        vector<int> temp;
        int val=0;
        if(!root) return res;
        FindPath(res, temp, root, expectNumber, val);
        return res;
    }
};