05 August 2008
给一个BST和一个double数，找到离double数最近的结点，返回差值
计算当前的结点和double的差值，然后根据BST的特性递归寻找子树中的最小值，然后比较二者。
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int closestValue(TreeNode root, double target) {
int currValue = root.val;
TreeNode child = target < currValue ? root.left : root.right;
if (child == null) {
return currValue;
}
int nextValue = closestValue(child, target);
return Math.abs(currValue - target) < Math.abs(nextValue - target) ? currValue : nextValue;
}
}