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

- 题目描述：

- 题目链接：

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=188&&tqId=36560&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking
- 设计思想：

详细操作流程看下图

-视频讲解链接B站视频讲解

- 代码：
c++版本:

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
     bool flag = false; //用于返回最后的结果
    void dfs(TreeNode* root,int sum,int cnt){
        if(root == NULL || flag == true) return; //如果节点为空或者flag已经为true直接返回
        cnt += root->val; //用于存储路径和
        if(root->left == NULL && root->right == NULL){//已经到达了叶子节点
            if(sum == cnt){//进行判断当前路径和是否等于给定的预期值
                flag = true; 
            }
        }else{
            dfs(root->left,sum,cnt);//递归左子树
            dfs(root->right,sum,cnt); //递归右子树
        }
    }
    bool hasPathSum(TreeNode* root, int sum) {
        dfs(root,sum,0);
        return flag;

    }
};

Java版本：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    boolean flag = false; //用于返回最后的结果
    void dfs(TreeNode root,int sum,int cnt){
        if(root == null || flag == true) return ; //如果节点为空或者flag已经为true直接返回
        cnt += root.val; //用于存储路径和
        if(root.left == null && root.right == null){ //已经到达了叶子节点
         if(sum == cnt){//进行判断当前路径和是否等于给定的预期值
                flag = true; 
            }
        }else{
            dfs(root.left,sum,cnt);//递归左子树
            dfs(root.right,sum,cnt); //递归右子树
        }
    }
    public boolean hasPathSum (TreeNode root, int sum) {
        dfs(root,sum,0);
        return flag;

    }
}

Python版本:

class Solution:
    Flag = False #用于返回最后的结果
    def hasPathSum(self , root , sum ):
        def dfs(root,sum,cnt):
            if root == None or self.Flag == True: return #如果节点为空或者flag已经为true直接返回
            cnt += root.val #用于存储路径和
            if root.left == None and root.right == None: #已经到达了叶子节点
                if cnt == sum : self.Flag = True #进行判断当前路径和是否等于给定的预期值
            else:
                dfs(root.left,sum,cnt) #递归左子树
                dfs(root.right,sum,cnt) #递归右子树

        dfs(root,sum,0)
        return self.Flag