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

• 112
• 257