A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
94 Binary Tree Inorder Traversal
100 Same Tree
114 Flatten Binary Tree to Linked List
116 Populating Next Right Pointers in Each Node
117 Populating Next Right Pointers in Each Node II
124 Binary Tree Maximum Path Sum
144 Binary Tree Preorder Traversal
145 Binary Tree Postorder Traversal
366 Find Leaves of Binary Tree
257 Binary Tree Paths
235 Lowest Common Ancestor of a Binary Search Tree
236 Lowest Common Ancestor of a Binary Tree
671 Second Minimum Node In a Binary Tree
662 Maximum Width of Binary Tree
101 Symmetric Tree
102 Binary Tree Level Order Traversal
103 Binary Tree Zigzag Level Order Traversal
104 Maximum Depth of Binary Tree
107 Binary Tree Level Order Traversal II
108 Convert Sorted Array to Binary Search Tree
110 Balanced Binary Tree
111 Minimum Depth of Binary Tree
112 Path Sum
113 Path Sum II
623 Add One Row to Tree
222 Count Complete Tree Nodes
450 Delete Node in a BST
156 Binary Tree Upside Down
536 Construct Binary Tree from String
543 Diameter of Binary Tree
545 Boundary of Binary Tree
105 Construct Binary Tree from Preorder and Inorder Traversal
106 Construct Binary Tree from Inorder and Postorder Traversal
606 Construct String from Binary Tree
655 Print Binary Tree
742 Closest Leaf in a Binary Tree
783 Minimum Distance Between BST Nodes
Graph
Two Pointers
Linked List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By GitBook
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为树的高度
Previous
742 Closest Leaf in a Binary Tree
Next
Graph
Last modified 2yr ago
Copy link
Contents
783. Minimum Distance Between BST Nodes
1. Question
2. Implementation
3. Time & Space Complexity