530. 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.

這題我覺得最關鍵的是 binary search tree,其實我本來不太知道這個明確的定義是甚麼所以維基百科的解釋。

  1. 若任意節點的左子樹不空,則左子樹上所有結點的值均小於它的根結點的值;
  2. 若任意節點的右子樹不空,則右子樹上所有結點的值均大於它的根結點的值;
  3. 任意節點的左、右子樹也分別為二元搜尋樹;
  4. 沒有鍵值相等的節點。

我剛開始以為只要符合 左比較小,右比較大即可,但是還要注意一個點就是,假設是左子樹其節點也必須小於他個根,右子樹也以此類推。

所以這題的想法大概就是用in-order(左>根> 右)來算即可。

因為目的是想要找出左邊最大的根右邊最小(因為要找最小差)。

public class Solution {
int min = Integer.MAX_VALUE;
Integer prev = null;

public int getMinimumDifference(TreeNode root) {
if (root == null) return min;

getMinimumDifference(root.left);

if (prev != null) {
min = Math.min(min, root.val - prev);
}
prev = root.val;

getMinimumDifference(root.right);

return min;
}

}

一個遞迴的寫法,趕快好好更熟悉遞迴阿

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.