LeetCode - Easy - 783. Minimum Distance Between BST Nodes

怼烎@ 2022-10-06 08:53 114阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/minimum-distance-between-bst-nodes/][https_leetcode.com_problems_minimum-distance-between-bst-nodes]

Given the `root` of a Binary Search Tree (BST), return the minimum 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, 100]`.
 *   0 < = N o d e . v a l < = 1 0 5 0 <= Node.val <= 10^5 0<=Node.val<=105

**Note:** This question is the same as 530: [https://leetcode.com/problems/minimum-absolute-difference-in-bst/][https_leetcode.com_problems_minimum-absolute-difference-in-bst]

## Analysis ##

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

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

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class MinimumDistanceBetweenBSTNodes { 
    	//方法一：前后续遍历模式递归
        public int minDiffInBST(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, minDiffInBST(root.left)), // 
        			minDiffInBST(root.right));
        	
            return min;
        }
        
        //方法二：中续遍历模式递归
        public int minDiffInBST2(TreeNode root) { 
        	int[] min = { Integer.MAX_VALUE};
        	Integer[] prev = { null};
        	minDiffInBST2(root, min, prev);
        	return min[0];
        }
        
        private void minDiffInBST2(TreeNode node, int[] min, Integer[] prev) { 
        	if(node == null) return;
        	minDiffInBST2(node.left, min, prev);
        	if(prev[0] != null)
        		min[0] = Math.min(min[0], node.val - prev[0]);
        	prev[0] = node.val;
        	minDiffInBST2(node.right, min, prev);
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class MinimumDistanceBetweenBSTNodesTest { 
    
    	@Test
    	public void test() { 
    		MinimumDistanceBetweenBSTNodes obj = new MinimumDistanceBetweenBSTNodes();
    
    		assertEquals(1, obj.minDiffInBST(BinaryTree.integers2BinaryTree(4,2,6,1,3)));
    		assertEquals(1, obj.minDiffInBST(BinaryTree.integers2BinaryTree(1,0,48,null,null,12,49)));
    	}
    	
    	@Test
    	public void test2() { 
    		MinimumDistanceBetweenBSTNodes obj = new MinimumDistanceBetweenBSTNodes();
    		
    		assertEquals(1, obj.minDiffInBST2(BinaryTree.integers2BinaryTree(4,2,6,1,3)));
    		assertEquals(1, obj.minDiffInBST2(BinaryTree.integers2BinaryTree(1,0,48,null,null,12,49)));
    	}
    }

[https_leetcode.com_problems_minimum-distance-between-bst-nodes]: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
[f2233d1bcd1930ff4b184a13723597b9.png]: /images/20221005/c978d5fe73f2404689718eda2dcec118.png
[488f03721e85771e6945d0f02ae7048b.png]: /images/20221005/061579db143a4ac49089084c3cb1846b.png
[https_leetcode.com_problems_minimum-absolute-difference-in-bst]: https://leetcode.com/problems/minimum-absolute-difference-in-bst/