Topic describes

Enter a binary tree and an integer, and print out the sum of node values in the binary tree as all paths to the input integers. A path is formed from the root of the tree down to the nodes passed by the leaf.

Example:

Given the following binary tree, and the target and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
Copy the code

Returns:

,4,11,2 [[5], [5,8,4,5]]Copy the code

Tip:

  1. The number of nodes is less than = 10000

solution

Sequential traversal + path record.

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        def dfs(root, sum):
            if root is None:
                return
            path.append(root.val)
            if root.val == sum and root.left is None and root.right is None:
                res.append(path.copy())
            dfs(root.left, sum - root.val)
            dfs(root.right, sum - root.val)
            path.pop()
        if not root:
            return []
        res = []
        path = []
        dfs(root, sum)
        return res
Copy the code

Java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private List<List<Integer>> res; private List<Integer> path; public List<List<Integer>> pathSum(TreeNode root, int sum) { if (root == null) return Collections.emptyList(); res = new ArrayList<>(); path = new ArrayList<>(); dfs(root, sum); return res; } private void dfs(TreeNode root, int sum) { if (root == null) { return; } path.add(root.val); if (root.val == sum && root.left == null && root.right == null) { res.add(new ArrayList<>(path)); } dfs(root.left, sum - root.val); dfs(root.right, sum - root.val); path.remove(path.size() - 1); }}Copy the code

JavaScript

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {number} sum * @return {number[][]} */ var pathSum = function (root, sum) { if (! root) return []; let res = []; function dfs(node, sum, arr) { if (! node) return; arr = [...arr, node.val]; if (node.val === sum && ! node.left && ! node.right) { res.push(arr); return; } dfs(node.left, sum - node.val, arr); dfs(node.right, sum - node.val, arr); } dfs(root, sum, []); return res; };Copy the code

C++

class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int target) { vector<vector<int>> ans; vector<int> path; dfs(root, ans, path, target); return ans; } void dfs(TreeNode* root, vector<vector<int>>& ans, vector<int>& path, int target) { if (root == NULL) { return; } target -= root->val; path.push_back(root->val); if (root->left == NULL && root->right == NULL) { if (target == 0) { ans.push_back(vector<int>(path)); } } dfs(root->left, ans, path, target); dfs(root->right, ans, path, target); path.pop_back(); }};Copy the code