272 Closest Binary Search Tree Value II

272. Closest Binary Search Tree Value II

1. Question

Given a non-empty binary search tree and a target value, findkvalues in the BST that are closest to the target.

Note:

• Given target value is a floating point.

• You may assume k is always valid, that is: k ≤ total nodes.

• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

• Follow up:

  Assume that the BST is balanced, could you solve it in less thanO(n) runtime (wheren= total nodes)?

2. Implementation

方法一： Inorder traversal

思路： 维护一个size为k的list，对树进行中序遍历，如果list的size等于k, 则比较list的第一个元素和当前node的值哪个更加接近target

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

        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;

        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
               stack.push(curNode);
               curNode = curNode.left;
            }
            else {
                curNode = stack.pop();

                if (res.size() < k) {
                    res.add(curNode.val);
                }
                else if (Math.abs(curNode.val - target) < Math.abs(res.getFirst() - target)) {
                    res.removeFirst();
                    res.add(curNode.val);
                }
                curNode = curNode.right;
            }
        }
        return res;
    }
}

3. Time & Space Complexity

时间和空间都是O(n)