山东网站建设找哪家,湛江市建设工程造价信息网,网站左侧导航栏设计,网页设计具体方案前言
关于路径的两道题。掌握递归函数要不要返回值。用到了defer关键字#xff0c;起到回溯的作用。
内容
一、路经总和
112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径#xff0c;这条路径上所…前言
关于路径的两道题。掌握递归函数要不要返回值。用到了defer关键字起到回溯的作用。
内容
一、路经总和
112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。
递归
确定递归函数的参数和返回类型
参数需要二叉树的根节点还需要一个计数器这个计数器用来计算二叉树的一条边之和是否正好是目标和计数器为int型。
再来看返回值递归函数什么时候需要返回值什么时候不需要返回值这里总结如下三点
如果需要搜索整棵二叉树且不用处理递归返回值递归函数就不要返回值。这种情况就是本文下半部分介绍的113.路径总和ii如果需要搜索整棵二叉树且需要处理递归返回值递归函数就需要返回值。 这种情况我们在236. 二叉树的最近公共祖先中介绍如果要搜索其中一条符合条件的路径那么递归一定需要返回值因为遇到符合条件的路径了就要及时返回。本题的情况
确定终止条件
首先计数器如何统计这一条路径的和呢
不要去累加然后判断是否等于目标和那么代码比较麻烦可以用递减让计数器count初始为目标和然后每次减去遍历路径节点上的数值。
如果最后count 0同时到了叶子节点的话说明找到了目标和。
func hasPathSum(root *TreeNode, targetSum int) bool {if rootnil{return false}
targetSum-root.Val
if root.Leftnilroot.RightniltargetSum0{return true
}return hasPathSum(root.Left,targetSum)||hasPathSum(root.Right,targetSum)
}
二、路经总和II
113.路径总和II
给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
递归
要遍历整个树找到所有路径所以递归函数不要返回值
func pathSum(root *TreeNode, targetSum int) [][]int {var result [][]intvar vals []intvar dfs func(node *TreeNode,sum int)dfsfunc(node *TreeNode,sum int){if nodenil{return }sum-node.Valvalsappend(vals,node.Val)defer func(){valsvals[:len(vals)-1]}()//defer语句用于在每次递归调用结束后将vals切片中最后添加的元素移除。即回溯到上一节点
if node.Leftnilnode.Rightnilsum0{resultappend(result,append([]int(nil),vals...))
}//将 vals 切片中的所有元素追加到一个新的切片中if node.Left!nil{dfs(node.Left,sum)}if node.Right!nil{dfs(node.Right,sum)}}dfs(root,targetSum)return result
}
最后
今天先这样吧
