題目

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:

Input: 1 \ 3 / 2
Output:1
Explanation:The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

解題思路

前序遍歷二叉搜素樹，得到一個從小到大的數(shù)組，遍歷數(shù)組，求兩個元素差值的最小值

代碼

minDiff.go

package _530_Minimum_Absolute_Difference_in_BST

import "fmt"

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

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var nodeSlice []int

func PreOrder(t *TreeNode)  {
    if nil == t {
        return
    }

    PreOrder(t.Left)
    nodeSlice = append(nodeSlice, t.Val)
    PreOrder(t.Right)
}
func GetMinimumDifference(root *TreeNode) int {
    nodeSlice = []int{}
    PreOrder(root)

    fmt.Printf("slice:%+v", nodeSlice)

    len1 := len(nodeSlice)

    minDiff := nodeSlice[1] - nodeSlice[0]
    for i := 2; i < len1; i++ {
        diff := nodeSlice[i] - nodeSlice[i-1]
        if diff < minDiff {
            minDiff = diff
        }
    }
    return minDiff
}

測試

minDiff_test.go

package _530_Minimum_Absolute_Difference_in_BST

import "testing"


func InitTree(index int, input []int) (t *TreeNode) {
    if index > len(input) {
        return nil
    }

    if input[index - 1] < 0 {
        return nil
    }
    t = new(TreeNode)
    t.Val = input[index - 1]

    t.Left = InitTree(index*2, input)
    t.Right = InitTree(index*2 + 1, input)

    return t
}

func TestGetMinimumDifference(t *testing.T) {
    input1 := []int{1, -1, 3, -1, -1, 2}
    input2 := []int{1, -1, 5, -1, -1, 3}
    var tests = []struct{
        input *TreeNode
        output int
    }{
        {InitTree(1, input1), 1},
        {InitTree(1, input2), 2},
    }
    for _, test := range tests {
        ret := GetMinimumDifference(test.input)
        if ret == test.output {
            t.Logf("pass")
        } else {
            t.Errorf("fail, want %+v, get %+v", test.output, ret)
        }
    }

}