783. Minimum Distance Between BST Nodes
Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.
Example :
Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.
The given tree [4,2,6,1,3,null,null] is represented by the following diagram:
4
/ \
2 6
/ \
1 3
while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.
Note:
- The size of the BST will be between 2 and 100.
- The BST is always valid, each node's value is an integer, and each node's value is different.
- This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
/**
* 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 {
public int minDiffInBST(TreeNode root) {
if(root==null||(root.left==null&&root.right==null)){
return 0;
}
ArrayList<Integer> ans = new ArrayList<>();
inorderTraversal(root, ans);
int minDiff = Integer.MAX_VALUE;
for(int i=0;i<ans.size()-1;i++){
int diff = ans.get(i+1) - ans.get(i);
if(diff<minDiff){
minDiff = diff;
}
}
return minDiff;
}
public void inorderTraversal(TreeNode root, ArrayList<Integer> ans){
if(root == null){
return;
}
inorderTraversal(root.left, ans);
ans.add(root.val);
inorderTraversal(root.right, ans);
}
}深度优先遍历，保存节点的值