NC9二叉树中是否存在节点和为指定值的路径

NC9二叉树中是否存在节点和为指定值的路径

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a?tpId=188&&tqId=36537&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

- 设计思想：

详细操作流程看下图:

- 代码：
c++版本:

 /**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型vector<vector<>>
     */
     vector<vector<int>>res; //返回最终结果
     vector<int>tmp; //用于临时存储路径
     void dfs(TreeNode* root,int sum,int cnt){
         if(root == NULL) return; // 如果节点为空结束当前递归
         tmp.push_back(root->val); //将当前节点加入tmp数组
         cnt += root->val; //把当前节点加入到路径和中
         if(root->left == NULL && root->right == NULL){ //当递归到没有子树的时候就需要判断
             if(sum == cnt){ //如果当前节点的路径和等于sum，那么就在res中插入tmp
                 res.push_back(tmp);
             }
         }else{              
             dfs(root->left,sum,cnt); //递归左子树
             dfs(root->right,sum,cnt); //递归右子树
         }
         cnt -= tmp[tmp.size()-1]; 
         tmp.pop_back();


     }
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        dfs(root,sum,0); //开始类似先序的递归
        return res;    
    }
};

Java版本：

import java.util.*;