530. 二叉搜索树的最小绝对差(树)(BST)
程序员文章站
2022-04-24 16:28:42
...
方法一:(中序遍历+额外o(n)的存储空间)
中序遍历BST ,得到的序列有序,所有相邻结点差的绝对值的最小值就是要找的结果
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int getMinimumDifference(TreeNode root) {
ArrayList<Integer> array = new ArrayList<>();
inOrder(root,array);
int res = Integer.MAX_VALUE;
if(array.size()<2) return -1;
for(int i = 1;i<array.size();i++){
if(array.get(i)-array.get(i-1)<res) res = array.get(i)-array.get(i-1);
}
return res;
}
public void inOrder(TreeNode root, ArrayList array){
if(root == null) return;
inOrder(root.left,array);
array.add(root.val);
inOrder(root.right,array);
}
}
方法二:中序遍历+只是用常数量辅助空间
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int res = Integer.MAX_VALUE;
private TreeNode pre = null;
public int getMinimumDifference(TreeNode root) {
inOrder(root);
return res;
}
public void inOrder(TreeNode root){
if(root == null) return;
inOrder(root.left);
if(pre!=null) res = Math.min(res,root.val-pre.val);
pre = root;
inOrder(root.right);
}
}