Skip to content

Instantly share code, notes, and snippets.

@brugnara
Created December 12, 2020 09:40
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save brugnara/c158f54317f1938754fb482e1b9a1949 to your computer and use it in GitHub Desktop.
[golang] Given a BT, let's found the ancestor for the deepest leave/s
/**
* 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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment