剑指offer——面试题25：二叉树中和为某一值的路径

参考网址：

Solution1:

Solution2写法更标准一些！

/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left(NULL), right(NULL) {    }};*/class Solution {public:    vector
   
    
      > buffer;    vector
     
       tmp;    vector
      
       
         > FindPath(TreeNode* root, int expectNumber) {        if (root == NULL)            return buffer;        tmp.push_back(root->val);        //如果是叶子结点，并且路径上结点和等于输入值        //打印这条路径        if ((expectNumber - root->val) == 0 &&             root->left==NULL && root->right==NULL) {            buffer.push_back(tmp);        }        //如果不是叶节点，则遍历它的子节点        FindPath(root->left, expectNumber - root->val);        FindPath(root->right, expectNumber - root->val);        //在返回父结点之前，在路径上删除当前结点        if(tmp.size() != 0)            tmp.pop_back();        return buffer;    }};

Solution2:

教科书一样的DFS + Backtracking算法

注意和Solution3的细微差别，Solution3中没有backtracking的体现

/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left(NULL), right(NULL) {    }};*/class Solution {public:    vector
   
    
      > FindPath(TreeNode* root,int expectNumber) {        vector
     
      
       > ret;        vector
       
         trace;        if(root)            dfs(root,expectNumber,ret,trace);        return ret;    }    void dfs(TreeNode* root,int s,vector
        
         
          > &ret,vector
          
            &trace) { trace.push_back(root->val); if(!root->left&&!root->right) { if(s==root->val) ret.push_back(trace); } if(root->left) dfs(root->left,s-root->val,ret,trace); if(root->right) dfs(root->right,s-root->val,ret,trace); trace.pop_back(); }};

Solution3:

20180901重做

DFS经典套路题目

/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left(NULL), right(NULL) {    }};*/bool cmp(vector
   
     &a, vector
    
      &b) {    return a.size() > b.size() ? true : false; }class Solution { public:    vector
     
      
        > FindPath(TreeNode* root,int expectNumber) {        if (!root) return {};        vector
       
        
          > res; vector
         
           temp; int residual = expectNumber; my_DFS(root, residual, res, temp); sort(res.begin(), res.end(), cmp); return res; } void my_DFS(TreeNode *root, int residual, vector
          
           
             > &res, vector
            
              temp) { if (!root->left && !root->right) { //到达叶子结点 if (residual == root->val) { temp.push_back(root->val); res.push_back(temp); } return; } else { //一般情况 temp.push_back(root->val); if (root->left) my_DFS(root->left, residual - root->val, res, temp); if (root->right) my_DFS(root->right, residual - root->val, res, temp); } }};