2021-凯发真人娱乐

2021-12-15： 路径总和 iii。给定一个的根 root ，和一个整数 targetsum ，求该二叉树里节点值之和等于 targetsum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。力扣437。

答案2021-12-15：

时间紧，具体见代码。

代码用golang编写。代码如下：

package main
import "fmt"
func main() {

    root := &treenode{val: 1}

    root.left = &treenode{val: 2}

    root.right = &treenode{val: 3}

    ret := pathsum(root, 3)

    fmt.println(ret)

}
type treenode struct {

    val   int

    left  *treenode

    right *treenode

}
func pathsum(root *treenode, sum int) int {

    presummap := make(map[int]int)

    presummap[0] = 1

    return process(root, sum, 0, presummap)

}
// 返回方法数

func process(x *treenode, sum int, preall int, presummap map[int]int) int {

    if x == nil {

        return 0

    }

    all := preall   x.val

    ans := 0

    if _, ok := presummap[all-sum]; ok {

        ans = presummap[all-sum]

    }

    if _, ok := presummap[all]; !ok {

        presummap[all] = 1

    } else {

        presummap[all] = presummap[all]   1

    }

    ans  = process(x.left, sum, all, presummap)

    ans  = process(x.right, sum, all, presummap)

    if presummap[all] == 1 {

        delete(presummap, all)

    } else {

        presummap[all] = presummap[all] - 1

    }

    return ans

}

执行结果如下：

左神java代码

2021-12-15： 路径总和 iii。给定一个二叉树的根节点 root ，和一个整数 targetsum ，求该二叉树里节点值之和等于 targetsum 的 路径 的数目。路径 不需要从根节点开的相关教程结束。