530 Minimum Absolute Difference in BST[EASY, WORTH REVIEWING]

短命女 2022-01-19 01:33 114阅读 0赞

这题是让找一个BST中两个node的Absolute difference，val之差的最小绝对值。

想到BST你一定要先想到inorder traverse是递增的。我看到这题第一个想法竟然是找每一个节点的左子树的最右结点，以及右子树的最左结点，这想法看似没错，但我不知道怎么写。

然后我想到inorder traverse的时候，发现自己竟然不能迅速写出中序遍历二叉树的代码。。想了半天才写出来。

遍历二叉树是这样的：

1 递归左子树
    2 做想做的事，比如visit node
    3 递归右子树
    复制代码

其中第二部不用递归了啊，只要做事就行了。

# AC的代码 #

一开始我把min和前一个结点的值都用做了全局成员变量，这样可以避免在参数中传递带来的思考复杂。

int min = Integer.MAX_VALUE;
    	int preVal = -1;
    
    	public int getMinimumDifference(TreeNode root) {
    		inOrder(root);
    		return min;
    	}
    
    	private void inOrder(TreeNode root) {
    		if (root == null) return;
    		inOrder(root.left);
    		if (preVal != -1) {
    			min = Math.min(root.val - preVal, min);
    		}
            preVal = root.val;
    
    		inOrder(root.right);
    	}
    复制代码

AC之后我尝试把全局变量搞成参数。 首先，

# 下面的代码是不行的 #

//错误的示范
        public int getMinimumDifference(TreeNode root) {
    		return inOrder(root, -1, Integer.MAX_VALUE);
    
    	}
    	private int inOrder(TreeNode root, int pre, int min) {
    		if (root == null) return 0;
    		inOrder(root.left, pre, min);
    		if (pre != -1) {
    			min = Math.min(root.val - pre, min);
    		}
    		pre = root.val;
    		inOrder(root.right, pre, min);
    		return min;
    	}
    复制代码

为什么，因为最后返回的min是第一次传进去的min也就是 Integer.MAX\_VALUE。记住，**递归永远是从什么地方进去就从什么地方出来**，所以传一个int类型的基本数据类型，它的内存地址每次递归都会随着int值的变化而变化的，那等你回到最初的起点的时候，return的min就仍然是第一次传入的min。

于是我把min改成了数组：

//错误的示范
    	public int getMinimumDifference(TreeNode root) {
    		int[] min = new int[1];
    		min[0] = Integer.MAX_VALUE;
    		return inOrder(root, -1, min);
    
    	}
    
    	private int inOrder(TreeNode root, int pre, int[] min) {
    		if (root == null) return 0;
    		inOrder(root.left, pre, min);
    		if (pre != -1) {
    			min[0] = Math.min(root.val - pre, min[0]);
    		}
    		pre = root.val;
    		inOrder(root.right, pre, min);
    		return min[0];
    	}
    复制代码

但这么做仍然不行，比如5,4,7会返回2而不是1. 为什么？还是参数的问题。当我遍历完了4回到5的时候，这时候pre又是-1了，而不是之前的4. 当然可以把pre也弄成数组，不过这就跟全局变量一样了。 那总结一个规律： **凡是想要维护一个值的，比如前一个状态的值，不要用参数传递，用全局变量吧。**

我看了下，solutions的代码基本都跟我的一模一样，用了两个全局变量。

另外，有个人提出了如果不是BST的follow up： 用TreeSet来实现，floor和ceil函数分别可以找比给定函数小的和大的那个最近的那个数。查找时间是O(NlogN)。我也想了这个问题，不过我是想遍历一遍放到arraylist里然后排序，这样总时间就是O(N2)了。

他下面用了preorder，其实我想了一下，中序和后序似乎也是可以的，反正每个结点都要跟其他结点对比一次。

public class Solution {
        TreeSet<Integer> set = new TreeSet<>();
        int min = Integer.MAX_VALUE;
        
        public int getMinimumDifference(TreeNode root) {
            if (root == null) return min;
            
            if (!set.isEmpty()) {
                if (set.floor(root.val) != null) {
                    min = Math.min(min, root.val - set.floor(root.val));
                }
                if (set.ceiling(root.val) != null) {
                    min = Math.min(min, set.ceiling(root.val) - root.val);
                }
            }
            
            set.add(root.val);
            
            getMinimumDifference(root.left);
            getMinimumDifference(root.right);
            
            return min;
        }
    }
    复制代码

转载于:https://juejin.im/post/5a31342151882534af25f48c