LeetCode - Easy - 530. Minimum Absolute Difference in BST

浅浅的花香味﹌ 2022-10-06 08:55 128阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/minimum-absolute-difference-in-bst/][https_leetcode.com_problems_minimum-absolute-difference-in-bst]

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:**

![f2233d1bcd1930ff4b184a13723597b9.png][]

Input: root = [4,2,6,1,3]
    Output: 1

**Example 2:**

![488f03721e85771e6945d0f02ae7048b.png][]

Input: root = [1,0,48,null,null,12,49]
    Output: 1

**Constraints:**

* The number of nodes in the tree is in the range \[ 2 , 1 0 4 \] \[2, 10^4\] \[2,104\].
 * 0 < = N o d e . v a l < = 1 0 5 0 <= Node.val <= 10^5 0<=Node.val<=105

## Analysis ##

方法一：中续遍历模式递归

方法二：前后续遍历模式递归

## Submission ##

import java.util.Stack;
 
 import com.lun.util.BinaryTree;
 import com.lun.util.BinaryTree.TreeNode;
 
 public class MinimumAbsoluteDifferenceInBST { 
 	
 	//方法一：中续遍历模式递归
 	public int getMinimumDifference3(TreeNode root) { 
 	int[] min = { Integer.MAX_VALUE};
 	Integer[] prev = { null};
 	getMinimumDifference3(root, min, prev);
 	return min[0];
 	}
 	
 	private void getMinimumDifference3(TreeNode node, int[] min, Integer[] prev) { 
 	if(node == null) return;
 	getMinimumDifference3(node.left, min, prev);
 	if(prev[0] != null)
 		min[0] = Math.min(min[0], node.val - prev[0]);
 	prev[0] = node.val;
 	getMinimumDifference3(node.right, min, prev);
 	}
 
 	//方法二：前后续遍历模式递归
 	public int getMinimumDifference4(TreeNode root) { 
 	int min = Integer.MAX_VALUE;
 	if(root == null) return min;
 	
 	TreeNode lp = root.left;
 	if(lp != null) { //查左子树最大值节点
 		while(lp.right != null) { 
 			lp = lp.right;
 		}
 		
 		min = Math.min(min, root.val - lp.val);
 	}
 	
 	TreeNode rp = root.right;
 	if(rp != null) { //查右子树最小值节点
 		while(rp.left != null) { 
 			rp = rp.left;
 		}
 		
 		min = Math.min(min, rp.val - root.val);
 	}
 	
 	min = Math.min(Math.min(min, getMinimumDifference4(root.left)), // 
 			getMinimumDifference4(root.right));
 	
 return min;
 	}
 	
 	
 	//以下为旧版本回答，保留记录
 	
 public int getMinimumDifference(TreeNode root) { 
 	
 	//There are at least two nodes in this BST.
 	boolean throwException = false;
 	if(root == null) { 
 		throwException = true;
 	}else { 
 		if(root.left == null && root.right == null) { 
 			throwException = true;
 		}
 	}
 	if(throwException) { 
 		throw new IllegalArgumentException();
 	}
 	
 	//正戏
 	int min = Integer.MAX_VALUE;
 	
 	Stack<TreeNode> stack = new Stack<>();
 	
 	while(true) { 
 		if(root.left == null && root.right == null) { 
 			if(stack.isEmpty()) { 
 				break;
 			}else { 
 				root = stack.pop();
 			}
 		}else if(root.left != null && root.right == null){ 
 			min = Math.min(getMinAbsDiff(root), min);
 			root = root.left;
 		}else if(root.left == null && root.right != null){ 
 			min = Math.min(getMinAbsDiff(root), min);
 			root = root.right;
 		}else { 
 			min = Math.min(getMinAbsDiff(root), min);
 			stack.push(root.right);
 			root = root.left;
 		}
 	}
 	
 return min;
 }
 
 
 private int getMinAbsDiff(TreeNode p) { 
 	
 	int a = p.val; 
 	Integer	leftDiff = null, rightDiff = null;
 	
 	TreeNode leftMaxNode = BinaryTree.max(p.left);
 	TreeNode rightMinNode = BinaryTree.min(p.right);
 	
 	if(leftMaxNode != null) { 
 		leftDiff = Math.abs(a - leftMaxNode.val);
 	}
 	
 	if(rightMinNode != null) { 
 		rightDiff = Math.abs(a - rightMinNode.val);
 	}
 	
 	
 	if(leftDiff != null && rightDiff == null) { 
 		return leftDiff;
 	}
 
 	if(leftDiff == null && rightDiff != null) { 
 		return rightDiff;
 	}
 	
 	return Math.min(leftDiff, rightDiff);
 	
 }
 
 //
 
 int minDiff = Integer.MAX_VALUE;
 TreeNode prev;
 
 /** * * Since this is a BST, the inorder traversal of its nodes results in a sorted list of values. Thus, the minimum absolute difference must occur in any adjacently traversed nodes. I use the global variable "prev" to keep track of each node's inorder predecessor. * * * 例如：输入的二叉树 *root->600 *          / \ *     424 612 *          \ / *     499 689 * * * 中序遍历后得 424 499 600 612 689 ，得出一个升序的数列。显然，最小值绝对差就由两个相邻的数的出。 * * @param root * @return */
 public int getMinimumDifference2(TreeNode root) { 
 inorder(root);
 return minDiff;
 }
 
 public void inorder(TreeNode root) { 
 if (root == null) return;
 inorder(root.left);
 if (prev != null) 
 	minDiff = Math.min(minDiff, root.val - prev.val);
 prev = root;
 inorder(root.right);
 }
 
 }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    
    public class MinimumAbsoluteDifferenceInBSTTest { 
    	
    	@Test
    	public void test() { 
    		MinimumAbsoluteDifferenceInBST mad =  new MinimumAbsoluteDifferenceInBST();
    		TreeNode root = BinaryTree.integerArray2BinarySearchTree(new int[] { 1, 3, 2});
    		assertEquals(1, mad.getMinimumDifference(root));
    		assertEquals(1, mad.getMinimumDifference2(root));
    		assertEquals(1, mad.getMinimumDifference3(root));
    		assertEquals(1, mad.getMinimumDifference4(root));
    	}
    	
    	@Test
    	public void test4() { 
    		MinimumAbsoluteDifferenceInBST mad = new MinimumAbsoluteDifferenceInBST();
    		TreeNode root = BinaryTree.integerArray2BinarySearchTree(new int[] { 236,104,701,227,911});
    		assertEquals(9, mad.getMinimumDifference(root));
    		assertEquals(9, mad.getMinimumDifference2(root));
    		assertEquals(9, mad.getMinimumDifference3(root));
    		assertEquals(9, mad.getMinimumDifference4(root));
    	}
    	@Test
    	public void test5() { 
    		MinimumAbsoluteDifferenceInBST mad = new MinimumAbsoluteDifferenceInBST();
    		TreeNode root = BinaryTree.integerArray2BinarySearchTree(new int[] { 600,424,612,499,689});
    		assertEquals(12, mad.getMinimumDifference(root));
    		assertEquals(12, mad.getMinimumDifference2(root));
    		assertEquals(12, mad.getMinimumDifference3(root));
    		assertEquals(12, mad.getMinimumDifference4(root));
    	}
    	
    	@Test(expected=IllegalArgumentException.class)
    	public void test2() { 
    		MinimumAbsoluteDifferenceInBST mad = new MinimumAbsoluteDifferenceInBST();
    		TreeNode root = BinaryTree.integerArray2BinarySearchTree(new int[] { 1});
    		mad.getMinimumDifference(root);
    		//assertEquals(1, mad.getMinimumDifference(root));
    	}
    	
    	@Test(expected=IllegalArgumentException.class)
    	public void test3() { 
    		MinimumAbsoluteDifferenceInBST mad = new MinimumAbsoluteDifferenceInBST();
    		TreeNode root = null;
    		mad.getMinimumDifference(root);
    		//assertEquals(1, mad.getMinimumDifference(root));
    	}
    	
    }

[https_leetcode.com_problems_minimum-absolute-difference-in-bst]: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
[f2233d1bcd1930ff4b184a13723597b9.png]: /images/20221005/e599dd2217314856b45a8cf7fe140f68.png
[488f03721e85771e6945d0f02ae7048b.png]: /images/20221005/35f06c8e0d774aeb93f74d6b1436a690.png