Force buckle 272 Closest binary search tree value II recursion

Power button 272. The closest binary search tree value II

Given the root of a binary search tree  root 、 A target value  target  And an integer  k , return BST Closest to target in  k  It's worth . You can press   In any order   Return to the answer .

subject   Guarantee   In this binary search tree, there is only one kind of  k Sets of values are the closest  target

Example 1：

 Input : root = [4,2,5,1,3], The target  = 3.714286, And  k = 2
 Output : [4,3]

Example 2:

 Input : root = [1], target = 0.000000, k = 1
 Output : [1]

Tips ：

• The total number of nodes in the binary tree is  n
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^9
• -109 <= target <= 10^9

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/closest-binary-search-tree-value-ii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source . 

The result of doing the question

adopt , Just pure tree recursion

Method 1-1： Merging recursion

Because both of them are recursive, let's divide them into small points

Merge type means to push directly from the child result to the father , Merge the results of parent-child merging

1. Before calculating the left subtree n individual , Before calculating the right subtree n individual , Add in the middle 2n+1 individual , The part beyond , By deleting the far left and right nodes

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);
        }
    }

  Method 1-2： Sliding window recursion

Keep... In the window k There is a feasible solution

1. The order in a binary search tree is equivalent to traversing an ordered array

2. front k Direct access

3. If exceeded k individual , Check if the larger value is closer to , If not, just quit , If yes, remove the first one and add a current value

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);
            } 
            
        }
    }