【BFS二叉树】113路径总和II

113路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

思路：

题目最终输出的是路径，因此用BFS遍历的时候，需要记录走到每个节点的路径；

又因为路径和是要等于某个目标值的，因此也需要记录目标和。

⇒ 走到每个节点时需要记录 该结点的路径和路径和。

⇒ BFS 里queue 记录 的节点 [ node , [ node.val],node.val]

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}

// 根据数组创建一颗树
const createTree = (arr) => {
  const len = arr.length
  if (len === 0) return null
  const root = new TreeNode(arr[0]) // 根节点
  const queue = [root] // 用于存储每一层的节点
  let i = 1 // 当前节点在数组中的索引
  while (i < len) {
    const node = queue.shift() // 取出当前层的第一个节点
    const leftVal = arr[i++] // 左子节点的值
    const rightVal = arr[i++] // 右子节点的值
    if (leftVal !== null) {
      const leftNode = new TreeNode(leftVal)
      node.left = leftNode
      queue.push(leftNode) // 将左子节点添加到队列中
    }
    if (rightVal !== null) {
      const rightNode = new TreeNode(rightVal)
      node.right = rightNode
      queue.push(rightNode) // 将右子节点添加到队列中
    }
  }
  return root
}

let arr = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
let root = createTree(arr)
// console.log(root) // 输出树的结构

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
  // 找出所有，遍历的时候记录路径，路径和，路径和用于判断是否满足条件
  let res = []
  if (!root) return res

  let queue = [[root,[root.val],root.val]]

  while (queue.length) {
    const [node,path,pathSum] = queue.shift()
    
    // 满足条件保存。
    if (node.left === null && node.right === null && pathSum === targetSum) {
      res.push(path)
    }
    
    // 将临近的节点加入queue
    if (node.left) {
      queue.push([node.left, path.concat([node.left.val]), pathSum + node.left.val])
    }
    if (node.right) {
      queue.push([node.right, path.concat([node.right.val]), pathSum + node.right.val])
    }
  }

  return res
}

注意：path.concat 返回的是数组，path.push返回的是数组的长度。

 console.log([5].push(3)) // 返回的是长度。
 console.log([5].concat(3)) // [5, 3]

 let list = [5]
 list.push(2)
 console.log(list) // 返回的是 [5,2]

二、二叉树标记将路径和中分的点

从根到叶子节点的通路上，有个节点可以把通路上的节点平分成两部分，将其标记，统计整棵树上的所有节点和减去标记节点的和

如图，绿色的即为标记的点，

节点3上边为 6+7=13，下边为11+2=13，因此将3标记

节点5上边为7，下边有4+3 = 7，因此标记

节点1上边为7+5+4 = 16，下边为16，标记

思路：

BFS遍历每个节点，如果某个节点是所在路径的中间点，那么该节点的前缀和是所在路径和-该节点的值后剩余数的 一半，因此对于每个节点来说，都需要记录前缀和、路径和以及该节点的值。

因为树上可能会出现值一样的不同节点，因此visitedMap 需要保存的key是节点，而不能是节点的值。

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}

// 根据数组创建一颗树
const createTree = (arr) => {
  const len = arr.length
  if (len === 0) return null
  const root = new TreeNode(arr[0]) // 根节点
  const queue = [root] // 用于存储每一层的节点
  let i = 1 // 当前节点在数组中的索引
  while (i < len) {
    const node = queue.shift() // 取出当前层的第一个节点
    const leftVal = arr[i++] // 左子节点的值
    const rightVal = arr[i++] // 右子节点的值
    if (leftVal !== null) {
      const leftNode = new TreeNode(leftVal)
      node.left = leftNode
      queue.push(leftNode) // 将左子节点添加到队列中
    }
    if (rightVal !== null) {
      const rightNode = new TreeNode(rightVal)
      node.right = rightNode
      queue.push(rightNode) // 将右子节点添加到队列中
    }
  }
  return root
}

let arr = [7, 6, 5, 3, null, 4, null, 11, null, 1, 3, 2, null, 16, null]
let root = createTree(arr)

const bisectTreePath = (root) => {
  const queue = [[root, [root], root.val, [root.val]]]
  
  // 因为可能出现相同值的不同结点，如果map值存放值，就可能会遗漏。因此map的key存放树节点。
  let markedMap = new Map()

  const res = []

  while (queue.length > 0) {
    const [node, path, pathSum, pre] = queue.shift()
    markedMap.set(node, false)
    
    // 遇到叶子结点将结果保存。
    if (node.left === null && node.right === null) {
      res.push([path, pathSum, pre])
    }

    if (node.left !== null) {
      queue.push([
        node.left,
        path.concat(node.left),
        pathSum + node.left.val,
        pre.concat(pre.at(-1) + node.left.val)
      ])
    }
    if (node.right !== null) {
      queue.push([
        node.right,
        path.concat(node.right),
        pathSum + node.right.val,
        pre.concat(pre.at(-1) + node.right.val)
      ])
    }
  }

  for (let i = 0; i < res.length; i++) {
    const [path, pathSum, pre] = res[i]
    // console.log(path[0].val,11)
    for (let j = 0; j < pre.length - 1; j++) {
      if (
        pre[j] * 2 + path[j + 1].val === pathSum &&
        !markedMap.get(path[j + 1])
      ) {
        markedMap.set(path[j + 1], true)
      }
    }
  }

  // 遍历markedMap
  let sum = 0
  for (let [key, value] of markedMap) {
    if (value === false) {
      sum += key.val
    }
  }
  return sum
}

console.log(bisectTreePath(root))