sum-root-to-leaf-numbers.go

// https://leetcode.com/problems/sum-root-to-leaf-numbers

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


func sumNumbers(root *TreeNode) int {
    return sumNumbersByRec(root, 0)
}

func sumNumbersByRec(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    
    if root.Left == nil && root.Right == nil {
        return sum * 10 + root.Val
    }
    
    sumLeft := sumNumbersByRec(root.Left, sum * 10 + root.Val)
    sumRight := sumNumbersByRec(root.Right, sum * 10 + root.Val)
    
    return sumLeft + sumRight
}

type LevelNode struct {
    node *TreeNode
    level int
}

func sumNumbersByStack(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    stack := []*LevelNode{}
    curr := &LevelNode{root, 0}
    prevLevel := -1
    value := 0
    sum := 0
    
    for curr != nil {
        if curr.node.Right != nil {
            stack = append(stack, &LevelNode{curr.node.Right, curr.level + 1})
        }
        
        if curr.node.Left != nil {
            stack = append(stack, &LevelNode{curr.node.Left, curr.level + 1})
        }
        
        for prevLevel >= curr.level {
            value /= 10
            prevLevel--
        }
           
        prevLevel = curr.level
        value = value * 10 + curr.node.Val
        
        if curr.node.Left == nil && curr.node.Right == nil {
            sum += value
        }
        
        n := len(stack)
        curr = nil
        
        if n > 0 {
            curr = stack[n - 1]
            stack = stack[:n - 1]
        }
    }
    
    return sum
}