leetcode

LeetCode 272. Closest Binary Search Tree Value II

Problem

LeetCode 272. Closest Binary Search Tree Value II

1. 题目简述

给出一颗二叉树，给出一个目标double类型的target，找出k个与其最近的节点值。例如：

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

2. 算法思路

中序遍历 + Stack + Queue

这道题和LeetCode 270看起来很像，只不过270是只要求一个最接近的数。

其实算法就是在一个有序数组里找出最接近target的k个数。在这个数组中和target的关系有两种，一种是大于，一种是小于等于。对于小于等于target的数，我们将其按顺序压入stack中；对于大于target的数，我们将其按顺序放入queue中。然后我们比较栈顶和队首的值，哪个更接近target，就取出哪个，直至k个。

Corner Cases:
注意栈和队列为空的情况！

3. 解法

  1. LeetCode 105 preorder + inorder
    使用Arrays.copyOfRange(int[] data, int start, int end)函数，写起来简洁，但是有点慢，而且耗空间大，因为要截取数组。

/**
 * 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 List<Integer> closestKValues(TreeNode root, double target, int k) {
        Queue<Integer> larger = new LinkedList<Integer>();
        List<Integer> result = new ArrayList<Integer>();
        Stack<Integer> smaller = new Stack<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (!stack.isEmpty() || root != null) {
            if (root == null) {
                root = stack.pop();
                if (root.val <= target) {
                    smaller.push(root.val);
                } else {
                    larger.add(root.val);
                }
                root = root.right;
            } else {
                stack.push(root);
                root = root.left;
            }
        }

        while (k-- > 0) {
            if (smaller.isEmpty()) {
                result.add(larger.poll());
                continue;
            }
            if (larger.peek() == null) {
                result.add(smaller.pop());
                continue;
            }
            int x1 = smaller.peek();
            int x2 = larger.peek();
            if (Math.abs(x1 - target) < Math.abs(x2 - target)) {
                result.add(x1);
                smaller.pop();
            } else {
                result.add(x2);
                larger.poll();
            }
        }

        return result;
    }
}