【530. 二叉搜索树中的最小绝对差】
Given the root
of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3] Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49] Output: 1
Constraints:
[2, 104]
.0 <= Node.val <= 105
Note: This question is the same as 783: Minimum Distance Between BST Nodes – LeetCode
这题求BST中任意两个子节点的最小差。其实跟上一题挺像的,也是需要记录全局的最小和上一次遍历的节点,利用BST的性质(inorder)进行递归。然而自己写的时候出现了以下几个问题:
1. if (root == null)时,需要return min,刚开始直接return 0了……
2. 刚开始写成了直接return Math.min(f(left), f(right)),submit完发现WA了,看了答案才发现需要严格进行inorder traversal,我这直接写成preorder了无法preserve order。
3. 另外也看到有人指出用全局变量其实不太好,如果要改成传函数参数的话,需要参数是mutable的,方便一边遍历一边更新。可以参考这个,用长度为1的array来保存:Java O(n) Time Inorder Traversal Solution – Minimum Absolute Difference in BST – LeetCode
2023.2.4
做783的时候再次遇到这个题,瞎写一通上来就WA,然后毫无思路,真不知道上次咋写的……
从头开始想一遍思路,大概就是既然我们要找最小差的两个数之差,那么由于它是BST,最小差肯定是在两个inorder traversal的相邻节点之间,于是相当于就只需要找相邻的两个节点之间的差值,于是需要一个prev来记录上次的节点。
感觉就是,不需要想的太复杂,以跟prev比较为核心,所以在prev那段需要min = Math.min,而递归左右两边的时候都不需要。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
TreeNode prev = null;
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root == null) {
return min;
}
min = getMinimumDifference(root.left);
if (prev != null) {
min = Math.min(min, Math.abs(root.val - prev.val));
}
prev = root;
min = getMinimumDifference(root.right);
return min;
}
}
迭代:
其实就是inorder的迭代方法,which早就忘了,这次就复习了一下。刚开始写成preorder了看了半天都不对……以及还是得用到prev啊。
2023.2.4
半抄答案地写出来了……嗯……就是记了个大概,但是没理解透吧。刚开始想了半天从stack里可以直接pop还是得先peek……果然还是脑子不清醒,对这个问题没有理解透彻。以及本来好好一个inorder一加上要判断min就又不会了……太蠢了……
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
TreeNode prev = null;
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root == null) {
return min;
}
Deque<TreeNode> stack = new ArrayDeque<>();
pushAllLeftNodes(root, stack);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (prev != null) {
min = Math.min(min, Math.abs(node.val - prev.val));
}
pushAllLeftNodes(node.right, stack);
prev = node;
}
return min;
}
private void pushAllLeftNodes(TreeNode node, Deque<TreeNode> stack) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
}