首页 > 其他分享 >【BFS二叉树】113路径总和II

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

时间:2024-03-13 22:59:29浏览次数:25  
标签:node BFS const val II 二叉树 null root 节点

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

相关文章

  • 数据结构之树(Topk问题, 链式二叉树)
    一.topk问题取N个数中最大(小)的前k个值,N远大于k这道题可以用堆的方法来解决,首先取这N个数的前k个值,用它们建堆时间复杂度O(k)之后将剩余的N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大,则将堆顶数据覆盖后向下调整时间复杂度(N-k)*log(N)总共的时间复杂度为O(......
  • 111. 二叉树的最小深度c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/intmin(inti,intj){if(i>j)returnj;returni;}intminDepth(structTreeNode*root){......
  • IIC SPI UART RS232 RS485的差异简介
    UART串口通信:异步通信,两根线(RXDTXD)交叉连接进行点对点的通信,通信双方要设置好相同的波特率(其实不用完全一样也可以只要相差不大,毕竟是通信双方不是同一时钟),发送数据一般是发送8位,有起始位、数据、检验、停止位。串口通信的抗干扰能力差,通信距离短。RS232协议:编程还是按串......
  • 代码随想录算法训练营第四十四天 | 377. 组合总和 Ⅳ ,518. 零钱兑换 II ,完全背包
    377.组合总和Ⅳ 已解答中等 相关标签相关企业 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合32位整数范围。 示例1:输入:num......
  • leetcode回溯法典型例题:39.组合总和、40组合总和 II、46.全排列、47.全排列 II
    leetcode回溯法典型例题:39.组合总和、40组合总和II、46.全排列、47.全排列II39.组合总和39.组合总和-力扣(LeetCode)思路构建组合使用递归的方式构建出所有组合。由题意可知,元素可以无限取用,所以我们构建的时候每确定一个数字,进入更深层递归的时候,每个数字都可以取用(此......
  • 广度优先搜索(BFS)在数据结构中的应用
    广度优先搜索(BreadthFirstSearch,简称BFS)是图论中最基本的搜索算法之一,它用于遍历或搜索给定的图形结构,如树或图。与深度优先搜索(DFS)相比,BFS以广度优先的方式逐层探索节点,即它会先访问离起始节点近的所有节点,再逐步访问离起始节点远的节点。算法原理BFS算法的核心思想是使用队......
  • 代码随想录算法训练营第七天 | 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之
    day7记录代码随想录第一题力扣454.四数相加II 给定四个包含整数的数组列表 A,B,C,D,计算有多少个元组(i,j,k,l) ,使得 A[i]+B[j]+C[k]+D[l]=0。为了使问题简单化,所有的A,B,C,D具有相同的长度 N,且0≤N≤500。所有整数的范围在-2^28到......
  • 142. 环形链表 IIc
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*detectCycle(structListNode*head){structListNode*slow=head,*fast=head;while(fast&&fast->next......
  • 洛谷题单指南-二叉树-P4715 【深基16.例1】淘汰赛
    原题链接:https://www.luogu.com.cn/problem/P4715题意解读:计算亚军得主,注意能力值最高的肯定是冠军,但能力值第二高的不一定是亚军,因为有可能中途就遭遇冠军。解题思路:根据题意,两两比赛,一轮后再按顺序两两比赛,形如一棵二叉树,但解题其实用不到二叉树的数据结构可以看出,最后参与......
  • yii2项目连接多个数据库
    web.php配置,引入或者直接设置db我的是引入$db=require__DIR__.'/db.php';components下设置'db'=>$db['db'],'db2'=>$db['db2'], db.php文件,设置成自己的数据库配置<?phpreturn['db'=>[......