【LeetCode-112 | 路径总和】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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:
    // 1.确定递归函数的入参及返回值
    /*
        递归函数什么时候需要返回值？什么时候不需要返回值？
            如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。
    */
    bool Traversal(TreeNode* node, int count) {
        
        // 2.确定函数的递归终止条件
        if(!node->left && !node->right && count == 0) return true;
        if(!node->left && !node->right) return false;

        // 3.确定单层递归逻辑
        if(node->left) {
            count -= node->left->val;
            if(Traversal(node->left, count)) return true;
            count += node->left->val;

        }

        if(node->right) {
            count -= node->right->val;
            if(Traversal(node->right, count)) return true;
            count += node->right->val;
        }

        return false;

    }
    
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        return Traversal(root, targetSum - root->val);
    }
};