算法篇：树之路径之和
算法：
算法采用递归，核心在于如何找到递归的终止条件，具体步骤如下：
1.采用递归的方式，sum的数值要随着遍历过的节点做递减操作，sum = sum-root.Val2.递归的终止条件sum==0是其中之一，如果要求是叶子节点的也需要加上
题目1:
https://leetcode-cn.com/problems/path-sum/
代码实现：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func hasPathSum(root *TreeNode, sum int) bool {if root == nil {return false}// 叶子节点的判断，排除非叶子节点==sum的情况if root.Left == nil && root.Right == nil {return sum == root.Val}res := sum - root.Valif hasPathSum(root.Left,res) {return true}if hasPathSum(root.Right,res) {return true}return false}
执行结果：
题目2:
https://leetcode-cn.com/problems/path-sum-ii/
代码实现：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/var res [][]intfunc pathSum(root *TreeNode, sum int) [][]int {res = [][]int{} // 为了清空 res 上次的数值if root == nil {return nil}// var res [][]intvar tmp []intdfs(root,sum,tmp)return res}func dfs(root *TreeNode, sum int, tmp []int) {if root == nil {return}tmp = append(tmp,root.Val)if sum == root.Val && root.Left == nil && root.Right == nil {r := make([]int, len(tmp)) // 防止tmp对应的共享内容被修改copy(r, tmp)res = append(res, r)return}dfs(root.Left,sum-root.Val,tmp)dfs(root.Right,sum-root.Val,tmp)return}
执行结果：
题目3:
https://leetcode-cn.com/problems/path-sum-iii/
代码实现：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func pathSum(root *TreeNode, sum int) int {if root == nil {return 0}result := countPath(root,sum)result += pathSum(root.Left,sum)result += pathSum(root.Right,sum)return result}func countPath(root *TreeNode, sum int) int {if root == nil {return 0}count := 0res := sum - root.Valif res == 0 {count = 1}return count + countPath(root.Left,res) + countPath(root.Right,res)}/*以当前节点作为头结点的路径数量以当前节点的左孩子作为头结点的路径数量以当前节点的右孩子作为头结点的路径数量*/
执行结果：
本文分享自微信公众号 - 灰子学技术（huizixueguoxue）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
