113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1Return:
代码语言：javascript复制[
[5,4,11,2],
[5,8,4,5]
]思路：
题目意思是求出所有根节点到叶子结点路径和为
sum的结果。递归求解，找到叶子节点比较sum就可以
代码：
go：
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, sum int) [][]int {
var res [][]int
if root == nil {
return res
}
recursive(root, &res, []int{root.Val}, root.Val, sum)
return res
}
func recursive(node *TreeNode, res *[][]int, incr []int, tempSum int, sum int) {
if node.Left == nil && node.Right == nil {
if tempSum == sum {
*res = append(*res, incr)
}
}
if node.Left != nil {
var incrLeft []int
incrLeft = append(incrLeft, incr...)
incrLeft = append(incrLeft, node.Left.Val)
recursive(node.Left, res, incrLeft, tempSum node.Left.Val, sum)
}
if node.Right != nil {
recursive(node.Right, res, append(incr, node.Right.Val), tempSum node.Right.Val, sum)
}
}
