leetcode-go/oj/microsoft-2019-sim/2/main.go

package main

import "fmt"

// Get the distance of two nodes in binary tree

var finalDist int

func main() {
	distOf(1, 12, 12)
	fmt.Println(finalDist, 0)
	distOf(1, 12, 6)
	fmt.Println(finalDist, 1)
	distOf(1, 4, 5)
	fmt.Println(finalDist, 2)
	distOf(1, 1, 11)
	fmt.Println(finalDist, 3)
	distOf(1, 5, 6)
	fmt.Println(finalDist, 4)
	distOf(1, 6, 9)
	fmt.Println(finalDist, 5)
	distOf(1, 8, 15)
	fmt.Println(finalDist, 6)
}

//           __1__
//         _/     \_
//        /         \
//      _2_         _3_
//     /   \       /   \
//    4     5     6     7
//   / \   / \   / \   / \
//  8   9 10 11 12 13 14 15
func distOf(root, p, q int) int {
	if p < root && q < root {
		return -1
	}
	left := distOf(root*2, p, q) + 1
	right := distOf(root*2+1, p, q) + 1
	if left != 0 && right != 0 {
		finalDist = left + right
		return left
	}
	if left != 0 {
		if root == p || root == q {
			finalDist = left
		}
		return left
	}
	if right != 0 {
		if root == p || root == q {
			finalDist = right
		}
		return right
	}
	if root == p || root == q {
		return 0
	}
	return -1
}