golang刷leetcode 技巧（36）二叉树中和为某一值的路径

golangLeetcode

发布于 2022-08-02 18:46:46

23600

代码可运行

文章被收录于专栏：golang算法架构leetcode技术phpgolang算法架构leetcode技术php

运行总次数：0

代码可运行

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：

节点总数 <= 10000

注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

解题思路：

1，此题只是，先序遍历的一个变形

2，递归执行，深度优先遍历，这个时候sum变为sum－root.Val

3，到达叶子节点的时候，判断sum==root.Val，是则将整个链路加入结果里，否则，继续遍历

4，需要注意一点了，go的slice传递的是值，但是数据引用的是同一份

5，copy的时候需要先make分配空间，否则copy不成功

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, sum int) [][]int {
   var p[]int
   var r [][]int

   r=dfs(root,sum,p,r)
   return r
}

func dfs(root *TreeNode, sum int,path []int,ret [][]int)[][]int{
    if root==nil {
       return ret
    }
    path=append(path,root.Val)
    if root.Left==nil && root.Right==nil {
         if sum==root.Val{
              p:=make([]int,len(path))
             copy(p,path)
         ret=append(ret,p)
        fmt.Println(1,":",path,p,sum,root,ret)
         }
        return ret
    }
    if root.Left==nil{
        return dfs(root.Right,sum-root.Val,path,ret)
    }

    if root.Right==nil{
        return dfs(root.Left,sum-root.Val,path,ret)
    }
    l:=dfs(root.Left,sum-root.Val,path,ret)
    r:=dfs(root.Right,sum-root.Val,path,ret)
    fmt.Println(ret,l,r)
    ret=append(ret,l...)
    ret=append(ret,r...)
    return ret
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-21，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树