劍指offer之面試題24：二叉樹中和為某一值的路徑

題目：

輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。

例如輸入下圖中二叉樹和整數(shù)22，則打印出兩條路徑，第一條路徑包含結(jié)點(diǎn)10、12，第二條路徑包含結(jié)點(diǎn)10、5和7。

思路：

1、判斷根結(jié)點(diǎn)是否為空

2、單一路徑要有vector<int> path保存；

3、多條路徑要有vector<vector<int>> ret保存并返回；

4、從根結(jié)點(diǎn)分析，由于每次遍歷都要先把結(jié)點(diǎn)的值進(jìn)行訪問所以是前序遍歷；

5、在遍歷的同時(shí)，需要保存訪問過結(jié)點(diǎn)的值，并且和expectNumber相減得到剩余expectNumber

6、只有根結(jié)點(diǎn)才用判斷最后的值和剩余expectnumber相等，不相等，pop出path

7、根結(jié)點(diǎn)相等即為遞歸退出條件

代碼：

/*
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> > FindPath(TreeNode* root,int expectNumber) 
    {
		vector<vector<int>> ret;
        vector<int> path;
        if(root==NULL)
        {
            return ret;
        }
        findLeaf(ret,path,root,expectNumber);
        return ret;
    }
    void findLeaf(vector<vector<int>> &ret,vector<int> &path,TreeNode *node,int left)
    {
        path.push_back(node->val);
        //終止條件
        if(left-node->val==0&&node->left==NULL&&node->right==NULL)
        {
            ret.push_back(path);
        }
        else
        {
            if(node->left)
            {
                int l=left-node->val;
                findLeaf(ret,path,node->left,l);
            }
            if(node->right)
            {
                int l=left-node->val;
                findLeaf(ret,path,node->right,l);
            }
        }
        //是葉子節(jié)點(diǎn)但是路徑和不一樣，pop這個(gè)葉子節(jié)點(diǎn)
        path.pop_back();
    }
};

精簡(jiǎn)版代碼：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
    vector<vector<int> >allRes;
    vector<int> tmp;
    void dfsFind(TreeNode * node , int left){
        tmp.push_back(node->val);
        if(left-node->val == 0 && !node->left && !node->right)
            allRes.push_back(tmp);
        else {
            if(node->left) dfsFind(node->left, left-node->val);
            if(node->right) dfsFind(node->right, left-node->val);
        }
        tmp.pop_back(); 
    }
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(root) dfsFind(root, expectNumber);
        return allRes;
    }
};