跳转至

112 路径总和

https://leetcode.cn/problems/path-sum/description/

做法:递归

本做法中的targetSum为剔除掉当前节点剩余的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 {
private:
    bool dfs(TreeNode* root, int targetSum){
        // 判断是否存在左节点
        if(root->left){
            // 如果左节点存在满足条件的路径,那么当前节点也存在满足条件的路径
            if(dfs(root->left, targetSum - root->left->val))
                return true;
        }
        // 右节点同理
        if(root->right){
            if(dfs(root->right, targetSum - root->right->val))
                return true;
        }
        // 如果当前节点为叶子节点
        if(!root->left && !root->right){
            if(targetSum == 0)
                return true;
            else 
                return false;
        }
        return false;       
    }
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 如果根节点没空,不存在题解
        if(!root)
            return false;
        return dfs(root, targetSum - root->val);
    }
};

或写成

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

        if (cur->left) { // 左
            count -= cur->left->val; // 递归,处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯,撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归,处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯,撤销处理结果
        }
        return false;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        return traversal(root, sum - root->val);
    }
};

简化版

/**
 * 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 == NULL) return false;
        if(!root->left && !root->right && targetSum == root->val)   return true;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};