Erlo

算法篇:树之路径之和

2020-08-11 18:00:19 发布   22 浏览  
页面报错/反馈
收藏 点赞

算法:


算法采用递归,核心在于如何找到递归的终止条件,具体步骤如下:

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.Val     if 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 [][]int     var tmp []int    dfs(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 := 0    res := sum - root.Val    if res == 0 {        count = 1    }    return count + countPath(root.Left,res) + countPath(root.Right,res)}/*以当前节点作为头结点的路径数量以当前节点的左孩子作为头结点的路径数量以当前节点的右孩子作为头结点的路径数量*/

执行结果:


本文分享自微信公众号 - 灰子学技术(huizixueguoxue)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

登录查看全部

参与评论

评论留言

还没有评论留言,赶紧来抢楼吧~~

手机查看

返回顶部

给这篇文章打个标签吧~

棒极了 糟糕透顶 好文章 PHP JAVA JS 小程序 Python SEO MySql 确认