当前位置: 代码迷 >> 综合 >> 【leecode 剑指offer】二叉树中和为某一值的路径
  详细解决方案

【leecode 剑指offer】二叉树中和为某一值的路径

热度:80   发布时间:2023-11-22 21:24:35.0

题目

二叉树中和为某一值的路径

描述

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
在这里插入图片描述

思路

本问题是典型的二叉树方案搜索问题,使用回溯法解决,其包含 先序遍历 + 路径记录 两部分

  • 先序遍历: 按照 “根、左、右” 的顺序,遍历树的所有节点。
  • 路径记录: 在先序遍历中,记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum时,将此路径加入结果列表。

本图摘录于leecode官网

算法流程:

pathSum(root, sum) 函数:

  • 初始化: 结果列表 pathes ,路径列表 path 。
  • 返回值: 返回 pathes 即可。

recur(root,sum,pathes,[]) 函数:

  • 递推参数: 当前节点 root ,当前目标值 sum 。
  • 终止条件: 若节点 root 为空,则直接返回。

递推工作:

  • 路径更新: 将当前节点值 root.val 加入路径 path ;
  • 目标值更新: sum= sum- root.val(即目标值 从 sum 减至 0 );
  • 路径记录: 当 ① root 为叶节点 且 ② 路径和等于目标值 ,则将此路径 path 加入 pathes 。
  • 先序遍历: 递归左 / 右子节点。

代码实现

// 先序遍历
var pathSum = function(root, sum) {
    if(!root){
    //当为空节点时返回空数组return [];}const pathes =[];//结果数组recur(root,sum,pathes,[])return pathes;
};
function recur(root,sum,pathes,path){
    if(!root){
    //当为空节点时不执行操作return;}path = [...path,root.val];//深拷贝,记录遍历路径if(!root.left&&!root.right&&sum===root.val){
    //当达到叶子节点时且路径的结果等于特定值时pathes.push(path);//将此路径加入到结果队列中return;}recur(root.left,sum-root.val,pathes,path);//递归遍历左子树recur(root.right,sum-root.val,pathes,path);//递归遍历右子树
}

缺点

空间和时间效率不是太高,后面考虑回溯算法实现。

  相关解决方案