给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22，              5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1返回:[   [5,4,11,2],   [5,8,4,5]]

/* * @lc app=leetcode id=113 lang=javascript * * [113] Path Sum II *//** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } */function backtrack(root, sum, res, tempList) {  if (root === null) return;  if (root.left === null && root.right === null && sum === root.val)    return res.push([...tempList, root.val]);  tempList.push(root.val);  backtrack(root.left, sum - root.val, res, tempList);  backtrack(root.right, sum - root.val, res, tempList);  tempList.pop();}/** * @param {TreeNode} root * @param {number} sum * @return {number[][]} */var pathSum = function (root, sum) {  if (root === null) return [];  const res = [];  backtrack(root, sum, res, []);  return res;};

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<vector<int>> pathSum(TreeNode* root, int sum) {        auto ret = vector<vector<int>>();        auto temp = vector<int>();        backtrack(root, sum, ret, temp);        return ret;    }private:    void backtrack(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& tempList) {        if (root == nullptr) return;        tempList.push_back(root->val);        if (root->val == sum && root->left == nullptr && root->right == nullptr) {            ret.push_back(tempList);        } else {            backtrack(root->left, sum - root->val, ret, tempList);            backtrack(root->right, sum - root->val, ret, tempList);        }        tempList.pop_back();    }};

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:        if not root:            return []        result = []        def trace_node(pre_list, left_sum, node):            new_list = pre_list.copy()            new_list.append(node.val)            if not node.left and not node.right:                # 这个判断可以和上面的合并，但分开写会快几毫秒，可以省去一些不必要的判断                if left_sum == node.val:                    result.append(new_list)            else:                if node.left:                    trace_node(new_list, left_sum-node.val, node.left)                if node.right:                    trace_node(new_list, left_sum-node.val, node.right)        trace_node([], sum, root)        return result