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))
标签:node,BFS,const,val,II,二叉树,null,root,节点
From: https://blog.csdn.net/qq_43720551/article/details/136693855