Leetcode 113. 路径总和 II

题目

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

思路

• 首先创建一个vector<vector> resuLt结果数组，用来保存路径path数组
• 先序遍历，首先判断当前节点的左子树和右子树是不是空，count是否为0，如果是，说明找到了一条路径，存储该路径
• 递归遍历左子树，首先将当前节点存入path中，计数器count减去当前节点值，然后递归遍历，如果返回了不成功,直接撤销上次存储的结果。

代码

/** * Definition for a binary tree node. * 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:
    vector<vector<int>> result;
    vector<int> path;

    void traversal(TreeNode* cur,int count)
    {
    
        // 遇到叶子节点 并且count = 0 保存路径
        if(!cur->left && !cur->right && count == 0)
        {
    
            result.push_back(path);
            return;
        }
        // 遇到叶子节点且，且没有找到合适的边，直接返回
        if(!cur->left && !cur->right)
        {
    
            return;
        }
        if(cur->left)
        {
    
            // 递归遍历左子树
            path.push_back(cur->left->val);// 存入当前节点值
            count -= cur->left->val;

            traversal(cur->left,count); // 递归

            count += cur->left->val;// 回溯
            path.pop_back();// 回溯

        }
        if(cur->right)
        {
    
            // 递归遍历右子树
            path.push_back(cur->right->val);
            count -= cur->right->val;

            traversal(cur->right,count);// 递归

            count += cur->right->val;// 回溯
            path.pop_back();// 回溯
        }

        return;
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    
        result.clear();
        path.clear();
        if(root == NULL)
        {
    
            return result;
        }
        path.push_back(root->val);// 将根节点送入路径中
        traversal(root,targetSum - root->val);
        return result;
    }
};