首页 > itarticle > [leetcode] problem 783 – minimum distance between bst nodes

[leetcode] problem 783 – minimum distance between bst nodes

admin 11月 13, 2020 0

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:

1
2
3
4
5
 
      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

  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node’s value is an integer, and each node’s value is different.

Code

1
2
3
4
5
6
 
public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
private int min = Integer.MAX_VALUE;
private int prev = -1;

public int minDiffInBST(TreeNode root) {
    inorder(root);
    return min;
}

private void inorder(TreeNode root) {
    if (root == null)
        return;

    inorder(root.left);

    if (prev != -1)
        min = Math.min(min, root.val - prev);

    prev = root.val;

    inorder(root.right);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能