in order traversal, beat 97%, JAVA


  • 0
    I

    in order traversal, it is like maintain a window size of K, and keep updating farthest node of the linkedlist, time O(n).

    public class Solution {
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            LinkedList<Integer> result = new LinkedList<>();
            if (root == null) {
                return result;
            }
            dfs(result, root, target, k);
            return result;
        }
        private void dfs(LinkedList<Integer> result, TreeNode root, double target, int k) {
            if (root == null) {
                return;
            }
            dfs(result, root.left, target, k);
            if (result.size() == k) {
                if (Math.abs(result.getFirst() - target) >= Math.abs(root.val - target)) {
                    result.removeFirst();
                } else {
                    return;
                }
            }
            result.add(root.val);
            dfs(result, root.right, target, k);
        }
    }
    

Log in to reply
 

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