力扣-112题路径总和（C++）- DFS、自顶向下

红太狼 2022-08-31 13:25 130阅读 0赞

题目链接：[https://leetcode-cn.com/problems/path-sum/][https_leetcode-cn.com_problems_path-sum]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
思路一：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        bool hasPathSum(TreeNode* root, int targetSum) {
        
            //思路：自顶向下
    
            //如果当前节点为空，则为false
            if(!root) return false;
            targetSum-=root->val;
            
            //如果左右都是叶子节点，即已走到底，需要判断是否为0
            if(!root->left&&!root->right) return targetSum==0;
            
            return root->left&&hasPathSum(root->left,targetSum)||root->right&&hasPathSum(root->right,targetSum);
    
        }
    };

思路二：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        bool hasPathSum(TreeNode* root, int targetSum) {
        
            if(root==nullptr) return false;
    
            if(root->left==nullptr&&root->right==nullptr)
            return targetSum==root->val;
    
            if(hasPathSum(root->left,targetSum-root->val))
            return true;
    
            if(hasPathSum(root->right,targetSum-root->val))
            return true;
    
            return false;
        }
    };

[https_leetcode-cn.com_problems_path-sum]: https://leetcode-cn.com/problems/path-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/3f85d3bd91c64e79a544a91375ab4f0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/8557aca1436f43db9713b74110814592.png