解题报告 - 最接近的二叉搜索树数值
LeetCode 最接近的二叉搜索树数值
@TOC
题目描述
给定一个不为空的二叉搜索树和一个目标值 target,请在该二叉搜索树中找到最接近目标值 target 的数值。
最接近的二叉搜索树数值
示例
1输入: root = [4,2,5,1,3],目标值 target = 3.71428623 44 / \5 2 56 / \71 389输出: 4
提示:
1给定的目标值 target 是一个浮点数2题目保证在该二叉搜索树中只会存在一个最接近目标值的数
一、解题关键词
1二叉搜索树
二、解题报告
1.思路分析
- 二叉树有顺序
- 中序遍历 可以保证顺序
- root.val 放到list中 进行排序
2.时间复杂度
3.代码示例
1class Solution { 2 //树的遍历 (递归) 3 //有序的 4 public int closestValue(TreeNode root, double target) { 5 6 List<Integer> nums = new ArrayList<>(); 7 inorder(root, nums); 8 return Collections.min(nums,new Comparator<Integer>() { 9 @Override10 public int compare(Integer o1,Integer o2){11 return Math.abs(o1 - target) < Math.abs(o2 - target)? -1:1;12 }13 });14 }15 void inorder(TreeNode root,List<Integer>nums){16 if (root == null) return;17 inorder(root.left,nums);18 nums.add(root.val);19 inorder(root.right,nums);20 }21}
4.知识点
1先序 中序 后序 (看根节点在哪里)
网友评论