Use the inorder search to solve this problem (6ms)


  • 1
    T

    Using Inorder traversal is the cleanest way to solve this problem, because, inorder traversal, traverses the tree in ascending order. Which mean, we can skip the all the nodes after we have filled up k nodes.
    First fill out the list with k nodes. Because the traversal is in ascending order, the top of the list has the biggest value. If a new node coming in, has a lower diff than the top of the list. Replace the top of the list with the new node

    here is a iterative solution

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        s1.push(root);
        List<Integer> list = new ArrayList<Integer>(k);
    
        while (!s1.isEmpty()){
            TreeNode top = s1.peek();
    
            if (null != top.left){
                s1.push(top.left);
                top.left = null;
            }else {
                TreeNode visit = s1.pop();
    
                if (list.size() < k){
                    list.add(visit.val);
                }else {
                    if (Math.abs(list.get(0) - target) > Math.abs(visit.val - target)){
                        list.remove(0);
                        list.add(visit.val);
                    }else {
                        break;
                    }
                }
    
                if (null != visit.right){
                    s1.push(visit.right);
                }
            }
        }
    
        return list;
    }
    

    And here is a Recursive solution

    
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> list = new ArrayList<Integer>(k);
        helper(root, target, k, list);
                return list;
    }
    
    private void helper(TreeNode node, double target, int k, List<Integer> list){
        if (null == node){
            return;
        }
    
        helper(node.left, target, k, list);
        // visit
        if (list.size() < k){
            list.add(node.val);
        }else {
            double curDiff = Math.abs(node.val - target);
            double topDiff = Math.abs(list.get(0) - target);
    
            if (topDiff > curDiff){
                list.remove(0);
                list.add(node.val);
            }else {
                return;
            }
        }
        helper(node.right, target, k, list);
    }
    

Log in to reply
 

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