推 JIWP: 大師 06/14 10:54
推 DDFox: 大師 06/14 12:36
推 NTHUlagka: 大師 06/14 18:18
https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/
530. Minimum Absolute Difference in BST
找出一顆BST裡面任意兩個node最小的差。
Example 1:
https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg
Input: root = [1,0,48,null,null,12,49]
Output: 1
思路：
1.用BST中序走訪會按照順序走訪的特性，我們可以得到一個按照順序排列的序列，
任意值相差最小的數一定在他的左右兩邊，判斷前一個數與當前數的差並取小即可。
Java Code：
-----------------------------------------------------
class Solution {
private TreeNode prev;
private int res;
public int getMinimumDifference(TreeNode root) {
res = Integer.MAX_VALUE;
dfs(root);
return res;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (prev != null) {
res = Math.min(res, root.val - prev.val);
}
prev = root;
dfs(root.right);
}
}
-----------------------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1686711159.A.35D.html