剑指 Offer 34. 二叉树中和为某一值的路径

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

在没有子节点的节点处就判断，当前值是否和节点值相等，此处不用再往下递进，可以return

在有子节点的节点处，需要一直递进，直到碰到“叶子节点”进行判断后返回，或者直到递进到nullptr后返回false

class Solution {
public:
    // 根据题目要求，这棵树一定要有 没有子节点的节点，才能返回true
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr){
            return false;
        }
        // 这就是 没有子节点的节点，到这里就可以返回了，不用继续递归到当前节点为nullptr
        if(root->left == nullptr && root->right == nullptr){
            return root->val == targetSum;
        }
        // 由于只需要存在一条路径即可，用逻辑或 ||
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

先序遍历过程中，随着递进和回溯，path数组会不断加入节点以及清除节点，反映了当前正在处理哪个节点

递归过程形参target的值也会改变，在不同节点target的值不一样，一旦发现到达叶节点，且当前节点的值与target相等，就用ans数组保存当前的path

class Solution {
public:
    vector> ans;
    vector path;

    vector> pathSum(TreeNode* root, int target) {
        if(root == nullptr){
            return ans;
        }
        path.push_back(root->val);
        if(root->left == nullptr && root->right == nullptr && root->val == target){
        	// 题目定义的叶节点
            ans.push_back(path);
        }else{
        	// 不是叶节点，继续递
            pathSum(root->left, target - root->val);
            pathSum(root->right, target - root->val);
        }
        path.pop_back();
        return ans;
    }
};