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

孜孜不倦fly / 2023-08-15 / 原文

题目:

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void traversal(TreeNode* cur, int sum){
        if(!cur->left&&!cur->right&&sum==0){     //如果是叶子结点，且此时和减去该节点值为0了，则将该条路径添加到result中
            result.push_back(path);
            return;
        }
        if(!cur->left&&!cur->right){       //如果是叶子结点，但和不为0，则返回
            return;
        }
        if(cur->left){
            path.push_back(cur->left->val);     //若左节点存在，将其添加到path中
            traversal(cur->left,sum-cur->left->val);      //对左节点进行递归，注意传入的是sum-cur->left->val，所以sum的值在本次递归中没有被改变。包含了回溯的思想
            path.pop_back();      //回溯path数组
        }
        if(cur->right){      //若右节点存在，做相同处理
            path.push_back(cur->right->val); 
            traversal(cur->right,sum-cur->right->val);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        result.clear();
        path.clear();
        if(!root) return result;
        path.push_back(root->val);      //首先添加根节点的值到path中
        traversal(root, target-root->val);
        return result;
    }
};

以上方法来自代码随想录