描述
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13
| Input:
1 \ 3 / 2
Output: 1
Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
|
分析
求二叉树相邻节点间差值绝对值的最小值。因为中序遍历的结果是有序的,用中序遍历即可。
解决方案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 26 27 28 29 30
|
class Solution { private int result; private int prev; public int getMinimumDifference(TreeNode root) { result = Integer.MAX_VALUE; prev = Integer.MAX_VALUE; inOrder(root); return result; } private void inOrder(TreeNode root) { if (root == null) { return; } inOrder(root.left); result = Math.min(result, Math.abs(root.val-prev)); prev = root.val; inOrder(root.right); } }
|
相关问题