Leetcode C++『毎日一題』20200707 112.パスの合計

3769 ワード

タイトル
ツリーとターゲット和を指定し、ツリーにルートノードからリーフノードへのパスが存在するかどうかを判断します.このパスのすべてのノード値がターゲット和に加算されます.
説明:リーフノードとは、サブノードがないノードを指します.
例:次のツリーとターゲットとsum=22が与えられます.
          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

ターゲットと22のルートノードからリーフノードへのパス5->4->11->2があるため、trueを返します.
通過回数99108コミット回数197069
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/path-sum著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
構想
  • 簡単なテーマ、再帰的な考え方
  • 再帰の過程でsum=0ではなくnullが真であり,このノードは葉の結点から派生した子供ではない可能性がある
  • .
    コード#コード#
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            if (root == NULL) 
                return false;
            if (root->val == sum && root->left==NULL && root->right==NULL)
                return true;
            return  hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }
    };
    
    
    
    

    バグサンプル
    //bug
    /*
    []
    0
    */
    
    
    /*
    [1,2]
    1
    */