首页 > 代码库 > LeetCode Minimum Absolute Difference in BST
LeetCode Minimum Absolute Difference in BST
原题链接在这里:https://leetcode.com/problems/minimum-absolute-difference-in-bst/#/description
题目:
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
Input: 1 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.
题解:
Binary Tree Inorder Traversal, 由于是BST, 所以是asending的, 取出最小difference.
Time Complexity: O(n). Space: O(logn), stack space.
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 int min = Integer.MAX_VALUE; 12 Integer pre = null; 13 public int getMinimumDifference(TreeNode root) { 14 if(root == null){ 15 return min; 16 } 17 getMinimumDifference(root.left); 18 19 if(pre != null){ 20 min = Math.min(min, root.val-pre); 21 } 22 pre = root.val; 23 24 getMinimumDifference(root.right); 25 return min; 26 } 27 }
如果不是BST的话可以借助于TreeSet<Integer> ts, 对于每一个node, 找出node.val在ts中的floor和ceil, 计算minimum difference. 再把node 本身的val加到ts中.
Time Complexity: O(nlogn). Space: O(n), ts size.
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 int min = Integer.MAX_VALUE; 12 TreeSet<Integer> ts = new TreeSet<Integer>(); 13 14 public int getMinimumDifference(TreeNode root) { 15 if(root == null){ 16 return min; 17 } 18 19 if(!ts.isEmpty()){ 20 if(ts.floor(root.val) != null){ 21 min = Math.min(min, root.val-ts.floor(root.val)); 22 } 23 if(ts.ceiling(root.val) != null){ 24 min = Math.min(min, ts.ceiling(root.val)-root.val); 25 } 26 } 27 ts.add(root.val); 28 29 getMinimumDifference(root.left); 30 getMinimumDifference(root.right); 31 return min; 32 } 33 }
LeetCode Minimum Absolute Difference in BST
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。