Leetcode会员尊享100题：270.最接近的二叉树值

给你二叉搜索树的根节点root和一个目标值target，请在该二叉搜索树中找到最接近目标值target的数值。如果有多个答案，返回最小的那个。

示例 1：

输入：root = [4,2,5,1,3], target = 3.714286输出：4

示例 2：

输入：root = [1], target = 4.428571输出：1

提示：

• 树中节点的数目在范围[1, 104]内
• 0 <= Node.val <= 109
• -109 <= target <= 109

直接上代码：

/** * 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) { Info info = getInfo(root, target); return info.value; } public Info getInfo(TreeNode root, double target) { if(root == null) { return new Info(Integer.MAX_VALUE, Integer.MAX_VALUE); } if(root.left == null && root.right == null) { return new Info(root.val, Math.abs(root.val - target)); } /**拿到左右子树的信息 */ Info leftInfo = getInfo(root.left, target); Info rightInfo = getInfo(root.right, target); /**当前的最小差是左右树的最小差以及跟节点和target的差的最小值 */ double distance = Math.min(Math.abs(root.val - target), Math.min(leftInfo.distance, rightInfo.distance)); int value = distance == leftInfo.distance? leftInfo.value : distance == rightInfo.distance? rightInfo.value : root.val; /**有可能有重复的值，需要判断取最小那个 */ if(distance == leftInfo.distance) { value = Math.min(value, leftInfo.value); } if(distance == rightInfo.distance) { value = Math.min(value, rightInfo.value); } if(distance == Math.abs(root.val - target)) { value = Math.min(value, root.val); } /**返回当前树的信息 */ return new Info(value, distance); } } class Info { int value; double distance; public Info(int value, double distance) { this.value = value; this.distance = distance; } }

看不懂的请私信或者留言，二叉树的所有问题，我倾向于使用二叉树的递归套路，这个题其实可以用DFS，我懒得用