未分類

Minimum Absolute Difference in BST

BinarySearchTree, Go, LeetCode

Minimum Absolute Difference in BST

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

For Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

提示 解題應用
BinarySearchTree PreOrderTravel

Default:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
}

解答思路:

一開始思索著是否可以透過二元樹的關係找出值之間的最小距離，但是如果對於那些極端的狀況或參數是不適用的，所以就直接一邊前序遍歷所有的樹節點，一邊將該節點的值與先前遍歷的所有節點值找最小距離，如此一來在結束遍歷後也就能找出我們要的結果。

程式碼解說:

一開始先判斷根節點是否為nil，如果是就直接回傳0，接著便開始前序遍歷帶入根節點與用來儲存目前遍歷過所有節點的值及目前找到的最小值(這邊一開始放int的32位元極大值)

1
2
3
4
5
6
7
func getMinimumDifference(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var valList []int
	return preOrderTravel(root, valList, math.MaxInt32)
}

接下來的前序遍歷如果進來的節點為nil值就直接回傳最小值，如果該節點存在就利用一迴圈取出先前先遍歷過所有節點的值並與目前節點值相減取距離(絕對值取正數)，當該距離比目前找到的最小距離還小就將其取代，比對完目前能發現的最小距離後，接著才把目前節點值放入已遍歷的清單中，最後繼續做左右子節點的前序遍歷，這邊要注意的是當左子節點(樹)回傳最小結果後，將其帶入右子節點(樹)繼續判斷在另一側是否也為最小值，最後兩邊節點都比對過才向上回傳最小結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func preOrderTravel(node *TreeNode, valList []int, min int) int {
	if node == nil {
		return min
	}
	var diff int
	for _, v := range valList {
		diff = abs(node.Val - v)
		if diff < min {
			min = diff
		}
	}
	valList = append(valList, node.Val)
	min = preOrderTravel(node.Left, valList, min)
	min = preOrderTravel(node.Right, valList, min)
	return min
}

簡單的一個絕對值判斷，如果傳入的數小於0就乘上-1後回傳，其餘則直接回傳

1
2
3
4
5
6
func abs(num int) int {
	if num < 0 {
		return -num
	}
	return num
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func getMinimumDifference(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var valList []int
	return preOrderTravel(root, valList, math.MaxInt32)
}
func preOrderTravel(node *TreeNode, valList []int, min int) int {
	if node == nil {
		return min
	}
	var diff int
	for _, v := range valList {
		diff = abs(node.Val - v)
		if diff < min {
			min = diff
		}
	}
	valList = append(valList, node.Val)
	min = preOrderTravel(node.Left, valList, min)
	min = preOrderTravel(node.Right, valList, min)
	return min
}
func abs(num int) int {
	if num < 0 {
		return -num
	}
	return num
}

總結:

要找出一二元樹中任二節點值相減的距離為最小值，最簡單的做法就是直接一邊前序遍歷所有的樹節點，一邊將該節點的值與先前遍歷的所有節點值找最小距離，如此一來在結束遍歷後也就能找出我們要的結果。

分享到