85 lines
1.7 KiB
Go
85 lines
1.7 KiB
Go
|
package main
|
||
|
|
import (
|
||
|
|
"fmt"
|
||
|
|
"os"
|
||
|
|
"bufio"
|
||
|
|
"strings"
|
||
|
|
"strconv"
|
||
|
|
)
|
||
|
|
func main() {
|
||
|
|
//Enter your code here. Read input from STDIN. Print output to STDOUT
|
||
|
|
scanner := bufio.NewScanner(os.Stdin)
|
||
|
|
|
||
|
|
var nodes int
|
||
|
|
var tree *node
|
||
|
|
var target [2]int
|
||
|
|
|
||
|
|
for scanner.Scan() {
|
||
|
|
text := scanner.Text()
|
||
|
|
if nodes == 0 {
|
||
|
|
nodes, _ = strconv.Atoi(text)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
if tree == nil {
|
||
|
|
for _, s := range strings.Fields(text) {
|
||
|
|
v, _ := strconv.Atoi(s)
|
||
|
|
tree = insertNode(tree, &node{value:v})
|
||
|
|
}
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
for i, s := range strings.Fields(text) {
|
||
|
|
v, _ := strconv.Atoi(s)
|
||
|
|
target[i] = v
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if target[0]>target[1] {
|
||
|
|
target[0], target[1] = target[1], target[0]
|
||
|
|
}
|
||
|
|
fmt.Fprintln(os.Stderr, tree)
|
||
|
|
if n := lsa(tree, target); n != nil {
|
||
|
|
fmt.Println(n.value)
|
||
|
|
return
|
||
|
|
}
|
||
|
|
fmt.Println("nil")
|
||
|
|
}
|
||
|
|
|
||
|
|
type node struct{
|
||
|
|
value int
|
||
|
|
left *node
|
||
|
|
right *node
|
||
|
|
}
|
||
|
|
func insertNode(root, n *node) *node {
|
||
|
|
if root == nil {
|
||
|
|
return n
|
||
|
|
}
|
||
|
|
if root.value > n.value {
|
||
|
|
root.left = insertNode(root.left, n)
|
||
|
|
return root
|
||
|
|
}
|
||
|
|
root.right = insertNode(root.right, n)
|
||
|
|
return root
|
||
|
|
}
|
||
|
|
|
||
|
|
func (n *node) String() string {
|
||
|
|
if n == nil { return "nil" }
|
||
|
|
return fmt.Sprintf("%v (%v %v)", n.value, n.left, n.right)
|
||
|
|
}
|
||
|
|
|
||
|
|
func lsa(tree *node, target [2]int) *node {
|
||
|
|
if tree == nil {
|
||
|
|
return nil
|
||
|
|
}
|
||
|
|
|
||
|
|
if target[0]>tree.value {
|
||
|
|
return lsa(tree.right, target)
|
||
|
|
}
|
||
|
|
|
||
|
|
if target[1]<tree.value {
|
||
|
|
return lsa(tree.left, target)
|
||
|
|
}
|
||
|
|
|
||
|
|
return tree
|
||
|
|
}
|