[数据结构与算法]力扣 272. 最接近的二叉搜索树值 II 递归

力扣 272. 最接近的二叉搜索树值 II

给定二叉搜索树的根?root?、一个目标值?target?和一个整数?k?，返回BST中最接近目标的?k?个值。你可以按?任意顺序?返回答案。

题目?保证?该二叉搜索树中只会存在一种?k 个值集合最接近?target

示例 1：

输入: root = [4,2,5,1,3]，目标值 = 3.714286，且 k = 2
输出: [4,3]

示例 2:

输入: root = [1], target = 0.000000, k = 1
输出: [1]

提示：

• 二叉树的节点总数为?n
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^9
• -109?<= target <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/closest-binary-search-tree-value-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。?

做题结果

通过，就纯粹的树的递归

方法1-1：归并型的递归

因为两个都是递归就分一下小点

归并型的意思就是直接从子结果推到父，合并父子合并的结果

1. 计算出左子树前n个，计算右子树前n个，加上中间一共2n+1个，超出的部分，通过删除左右两侧较远的节点实现

class Solution {
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            Deque<Integer> ans = new LinkedList<>();
            if(root == null) return new ArrayList<>();
            List<Integer> left = closestKValues(root.left,target,k);
            List<Integer> right = closestKValues(root.right,target,k);
            ans.addAll(left);
            ans.add(root.val);
            ans.addAll(right);
            if(ans.size()<=k){
                return new ArrayList<>(ans);
            }

            while (ans.size()>k){
                double d1 = Math.abs(ans.getFirst()-target);
                double d2 = Math.abs(ans.getLast()-target);
                if(d1>d2){
                    ans.removeFirst();
                }else{
                    ans.removeLast();
                }
            }
            return new ArrayList<>(ans);
        }
    }

?方法1-2：滑窗型的递归

保持窗口内有k个可行解

1. 二叉搜索树中序相当于顺序遍历有序数组

2. 前面k个直接取

3. 如果超过k个，检查更大值是不是更接近，不是就直接退出，是就移除第一个加一个当前值

class Solution {
        List<Integer> result = new LinkedList<>();
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            dfs(root,target,k);
            return result;
        }

        public void dfs(TreeNode root, double target, int k) {
            if (root == null) return ;
            dfs(root.left,target,k);
            
            if (result.size() < k || Math.abs(result.get(0) - target) > Math.abs(root.val - target)) {
                if(result.size()==k) result.remove(0);
                result.add(root.val);
                dfs(root.right,target,k);
            } 
            
        }
    }