Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/14 10:52)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串347/719 (看更多)

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