【算法题】二叉树中和为某一值的路径(二)

这题说的是找出所有路径和为 target 的路径，这里的路径只能从根节点到叶子节点，这题和上一题类似：《二叉树中和为某一值的路径》。

我们从根节点开始往下累加路径上的节点值，并且还要记录这条路径上的节点，到叶子节点的时候如果累加的值等于 target ，说明这条路径就是我们找的，保存这条路径。

我们使用的是 List （Java语言使用的是List，C++使用的是Vector）来存储路径上的节点，因为它是引用传递，所以递归往下走的时候我们选择节点，递归往回走的时候要撤销选择。

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        dfs(root, target, 0, new ArrayList<>(), ans);
        return ans;
    }

    /**
     * @param node   当前节点
     * @param target
     * @param sum    从根节点到当前节点路径上的和
     * @param path   记录从根节点到当前节点路径上的节点值。
     * @param ans    返回的结果集。
     */
    public void dfs(TreeNode node, int target, int sum, List<Integer> path,
                    List<ArrayList<Integer>> ans) {
        if (node == null)
            return;
        path.add(node.val);// 记录该路径上的节点
        sum += node.val;// 累加从根节点到当前节点这条路径上所有节点的和。
        // 如果到达叶子节点，就不能往下走了，直接return
        if (node.left == null && node.right == null) {
            // 如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
            // 要把它放到ans中
            if (target == sum)
                ans.add(new ArrayList<>(path));
        } else {
            dfs(node.left, target, sum, path, ans);// 递归到左子节点
            dfs(node.right, target, sum, path, ans);// 递归到右子节点
        }
        path.remove(path.size() - 1);// 往回走撤销选择
    }

public:
    vector<vector<int>> FindPath(TreeNode *root, int target) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(root, target, 0, path, ans);
        return ans;
    }

    /**
     * @param node   当前节点
     * @param target
     * @param sum    从根节点到当前节点路径上的和
     * @param path   记录从根节点到当前节点路径上的节点值。
     * @param ans    返回的结果集。
     */
    void dfs(TreeNode *node, int target, int sum, vector<int> &path,
             vector<vector<int>> &ans) {
        if (node == nullptr)
            return;
        path.push_back(node->val);// 记录该路径上的节点
        sum += node->val;// 累加从根节点到当前节点这条路径上所有节点的和。
        // 如果到达叶子节点，就不能往下走了，直接return
        if (node->left == nullptr && node->right == nullptr) {
            // 如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
            // 要把它放到ans中
            if (target == sum)
                ans.push_back(path);
        } else {
            dfs(node->left, target, sum, path, ans);// 递归到左子节点
            dfs(node->right, target, sum, path, ans);// 递归到右子节点
        }
        path.pop_back();// 往回走撤销选择
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》