Simple Java solution with explanation


  • 1
    L

    Use a stack to keep the predecessor, and an queue to keep the successor.

    Do an inorder traversal, any value greater than target will be put into successor and the other will be put into predecessor.

    After the traversal, collect the data.

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> list = new ArrayList<Integer>();
        
        if (root == null || k <= 0) {
            return list;
        }
        
        Stack<Integer> predecessor = new Stack<Integer>();
        Queue<Integer> successor = new LinkedList<Integer>();
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            
            node = stack.pop();
            if (node.val <= target) {
                predecessor.push(node.val);
            } else {
                successor.add(node.val);
            }
    
            node = node.right;
        }
        
        while (k > 0) {
            if (predecessor.isEmpty()) {
                list.add(successor.poll());
            } else if (successor.isEmpty()) {
                list.add(predecessor.pop());
            } else if (Math.abs(successor.peek() - target) < Math.abs(predecessor.peek() - target)) {
                list.add(successor.poll());
            } else {
                list.add(predecessor.pop());
            }
            k--;
        }
        
        return list;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.