path_sum_ii.go

// https://leetcode.com/problems/path-sum-ii

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type PathNode struct {
    node *TreeNode
    parent *PathNode
    remain int
}

func pathSum(root *TreeNode, sum int) [][]int {
    if root == nil {
        return [][]int{}
    }
    
    queue := []*PathNode{
        &PathNode{
            node: root,
            remain: (sum - root.Val),
        },
    }
    
    result := [][]int{}
    
    for len(queue) > 0 {
        top := queue[0]
        queue = queue[1:]
        
        if top.node.Left != nil {
            queue = append(queue, &PathNode{
                node: top.node.Left,
                parent: top,
                remain: top.remain - top.node.Left.Val,
            })
        }
        
        if top.node.Right != nil {
            queue = append(queue, &PathNode{
                node: top.node.Right,
                parent: top,
                remain: top.remain - top.node.Right.Val,
            })
        }
        
        if top.node.Left == nil && top.node.Right == nil && top.remain == 0 {
            result = append(result, restorePath(top))
        }
    }
    
    return result
}

func restorePath(root *PathNode) []int {
    path := []int{}
    
    for root != nil {
        path = append([]int{root.node.Val}, path ...)
        root = root.parent
    }
    
    return path
}