LeetCode演算法題-Minimum Absolute Difference in BST(Java實現)
這是悅樂書的第253 次更新,第266 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第120題(順位題號是530)。給定具有非負值的二叉搜尋樹,找到任意兩個節點的值之間的最小絕對差。例:
輸入:
1 \ 3 / 2
輸出:1
說明:最小絕對差值為1,即2和1之間(或2和3之間)的差值。
注意:此BST中至少有兩個節點。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
題目的要求是任意兩個節點值之間的絕對值最小,所以間接變成了求一組資料的最小絕對值。使用棧(或者佇列)遍歷所有節點,將所有節點值存入list中,然後將list轉為Integer型別的陣列,再將陣列排序,然後計算相鄰兩元素的絕對值,找出其中的最小值。
public int getMinimumDifference(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null) { stack.push(node.left); } list.add(node.val); if (node.right != null) { stack.push(node.right); } } Integer[] nums = (Integer[])list.toArray(new Integer[list.size()]) ; Arrays.sort(nums); int min = Math.abs(nums[0]-nums[1]); for (int i=0; i<nums.length-1; i++) { min = Math.min(Math.abs(nums[i]-nums[i+1]), min); } return min; }
03 第二種解法
我們可以利用BST的中序遍歷特性,BST中序遍歷的節點是左根右排列,是有序的、遞增的一列資料。因此,我們可以利用遞迴方法,中序遍歷其節點,計算其相鄰兩個節點值的絕對值。因此我們需要保留其前一個節點的節點值,使用一個全域性變數來記錄。如果prev為null,表示當前遍歷到的為第一個節點,不為null的時候,就可以直接計算最小絕對值了。
Integer prev = null; int min = 0; public int getMinimumDifference2(TreeNode root) { traverse(root); return min; } private void traverse(TreeNode root) { if (root == null) { return; } traverse(root.left); if (prev != null) { if (min == 0) { min = Math.abs(root.val - prev); } else { min = Math.min(Math.abs(root.val - prev), min); } } prev = root.val; traverse(root.right); }
04 第三種解法
第二種解法還可以再優化下,將遞迴方法內建,同時min初始值為int型別的最大值,而不是第二種解法的0,可以省去一步判斷。
Integer prev2 = null; int min2 = Integer.MAX_VALUE; public int getMinimumDifference3(TreeNode root) { if (root == null) { return min2; } getMinimumDifference3(root.left); if (prev2 != null) { min2 = Math.min(Math.abs(root.val - prev2), min2); } prev2 = root.val; getMinimumDifference3(root.right); return min2; }
05 小結
演算法專題目前已日更超過三個月,演算法題文章120 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!