signed

QiShunwang

“诚信为本、客户至上”

112. Path Sum

2021/1/28 12:07:50   来源:

112. 路径总和

题目描述

从根节点到叶子节点,加起来能不能满足targetsum。

思路

这个题目一开始没看明白,以为是只要有路径就行,没想到是结尾得是叶子节点,用广搜做的…

改进

递归的方法。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;

        if (!root->left && !root->right && root->val == sum) return true;

        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};