783 Minimum Distance Between BST Nodes

1. Question

Given a Binary Search Tree (BST) with the root noderoot, return the minimum difference between the values of any two different nodes in the tree.
Example :
1
Input: root = [4,2,6,1,3,null,null]
2
3
Output: 1
4
5
Explanation:
6
7
Note that root is a TreeNode object, not an array.
8
9
The given tree [4,2,6,1,3,null,null] is represented by the following diagram:
10
11
4
12
/ \
13
2 6
14
/ \
15
1 3
16
17
while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.
Copied!
Note:
  1. 1.
    The size of the BST will be between 2 and 100.
  2. 2.
    The BST is always valid, each node's value is an integer, and each node's value is different.

2. Implementation

(1) Inorder Traversal
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public int minDiffInBST(TreeNode root) {
12
int res = Integer.MAX_VALUE;
13
14
TreeNode curNode = root, preNode = null;
15
Stack<TreeNode> stack = new Stack<>();
16
17
while (curNode != null || !stack.isEmpty()) {
18
if (curNode != null) {
19
stack.push(curNode);
20
curNode = curNode.left;
21
}
22
else {
23
curNode = stack.pop();
24
if (preNode != null) {
25
res = Math.min(res, Math.abs(preNode.val - curNode.val));
26
}
27
preNode = curNode;
28
curNode = curNode.right;
29
}
30
31
}
32
return res;
33
}
34
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), n为树的node的个数,空间复杂度O(h), h为树的高度