描述
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 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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.
分析
要找最小的差值,如果序列是有序的,直接找最小的相邻的两个节点的差值即可。中序遍历的序列刚好是有序的。
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
class Solution { Integer result = Integer.MAX_VALUE, pre = null; public int minDiffInBST(TreeNode root) { if (root.left != null) { minDiffInBST(root.left); } if (pre != null) { result = Math.min(result, root.val - pre); } pre = root.val; if (root.right != null) { minDiffInBST(root.right); } return result; } }
|
相关问题