[golang] Given a BT, let's found the ancestor for the deepest leave/s

lowest-common-ancestor-of-deepest-leaves.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    levels := map[int][]*TreeNode{}
    walk(root, &levels, 0)
    
    // fmt.Println(levels)
    
    ln := len(levels)
    
    if ln == 1 {
        return root
    }
    
    if len(levels[ln-1]) == 1 {
        return levels[ln-1][0]
    }
    
    // search until we found a "father"
    index := ln - 1
    for {
        for _, leaf := range levels[index] {
            if containsAll(leaf, levels[ln-1]) {
                return leaf
            }
        }
        //
        index--
        if index == 0 {
            break
        }
    }
    
    return root
}

func containsAll(leaf *TreeNode, nodes []*TreeNode) bool {
    array := []*TreeNode{}
    toArray(leaf, &array)
    hash := map[*TreeNode]bool{}
    for _, a := range array {
        for _, n := range nodes {
            if a == n {
                hash[a] = true
            }
        }
    }
    return len(hash) == len(nodes)
}

func toArray(leaf *TreeNode, array *[]*TreeNode) {
    if leaf == nil {
        return
    }
    toArray(leaf.Left, array)
    *array = append(*array, leaf)
    toArray(leaf.Right, array)
}

func walk(leaf *TreeNode, levels *map[int][]*TreeNode, level int) {
    if leaf == nil {
        return
    }
    walk(leaf.Left, levels, level + 1)
    (*levels)[level] = append((*levels)[level], leaf)
    walk(leaf.Right, levels, level + 1)
}