题目

leetcode:113

代码与解析

这道题可以看做leetcode112和leetcode257合体
leetcode257
leetcode112

这道题要遍历整棵树, 把所有符合条件的路径添加进去, 所以不需要返回值

递归三部曲:

  • 确定参数和返回值
    要传入 当前节点, 和总和, 不需要返回值

  • 确定终止条件
    如果当前节点没有叶子结点,并且和等于target. 那么添加进res, 并返回
    如果当前节点没有叶子结点, 就返回

  • 确定单层递归逻辑
    我采用的前序遍历, 先处理中间节点,把当前节点添加进path,如果当前节点没有叶子结点,并且和等于target. 那么添加进res, 并返回,
    然后判断做节点左节点是否为空, 不空就遍历,并且加上回溯,遍历完恢复原样,我代码里写到逻辑这里是两处回溯,一个是path, 一个是sum,右节点也是如此

func pathSum(root *TreeNode, targetSum int) [][]int {
    res := [][]int{}
    if root==nil{
        return res
    }
    path := []int{}
    var traversal func(root *TreeNode, sum int)
    traversal = func(root *TreeNode, sum int){
        path = append(path, root.Val)
        // 如果当前节点没有叶子结点,并且和等于target. 那么添加进res, 并返回
        if sum ==targetSum&&root.Left==nil&&root.Right==nil{
            tmp := []int{}
            for _, value:=range path{
                tmp = append(tmp, value)
            }
            res = append(res, tmp)
            return 
        }
        // 如果当前节点没有叶子结点, 就返回
        if root.Left==nil&&root.Right==nil{
            return
        }
        if root.Left!=nil{
            // 一个回溯是sum, 一个是path
            traversal(root.Left, sum+root.Left.Val)
            path = path[:len(path)-1]
        }
        if root.Right!=nil{
            traversal(root.Right, sum+root.Right.Val)
            path = path[:len(path)-1]
        }
    }
    traversal(root, root.Val)
    return res
}
分类: 算法

站点统计

  • 文章总数:313 篇
  • 分类总数:19 个
  • 标签总数:193 个
  • 运行天数:1080 天
  • 访问总数:238764 人次

浙公网安备33011302000604

辽ICP备20003309号