解题报告 - 最接近的二叉搜索树数

解题报告 - 最接近的二叉搜索树数值

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.思路分析

1. 二叉树有顺序
2. 中序遍历 可以保证顺序
3. 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先序 中序 后序 （看根节点在哪里）

---