題目連結:
題目意譯:
給定一棵沒有負值的二元搜尋樹(Binary Search Tree,BST),找到最小的兩個節點之差值絕對值。
注:
BST 中至少有兩個節點。
範例測資:
輸入:
1
\
3
/
2
輸出:
1
解釋:
最小差值絕對值為 1 ,其為 2 與 1 之差值(或是 2 與 3 的差值)。
解題思維:
這題有提及過,二元搜尋樹有一個特性,其中序探訪所得的序列為一個排好序的數列。
因此,我們只要進行中序探訪,然後對於每兩對相鄰的數字求差值絕對值,看哪個最小即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。