113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

Return:

[
[5,4,11,2],
[5,8,4,5]
]

Analyze

思路: 结合 DFS 中的先序遍历将所有解推入数组中。

/**
* 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) {
const result = []
if (!root) return []
analyzeSum(root, '', result, sum)
return result.map(val => {
return val.split('->')
})
};
/**
* node: analyze node
* str: join str using '->', affected by [257.Binary Tree Paths](https://github.com/MuYunyun/blog/blob/master/LeetCode/257.Binary_Tree_Paths.md)
* result: result array
* extra: extra sum need to satisfy
*/
var analyzeSum = function(node, str, result, extra) {
if (!node) return
if (!node.left && !node.right && extra === node.val) {
str += node.val
result.push(str)
return
}
str += `${node.val}->`
analyzeSum(node.left, str, result, extra - node.val)
analyzeSum(node.right, str, result, extra - node.val)
}

link