Java one stack InOrder O(n) accepted solution


  • 0
    M

    The basic idea is while doing inorder traversal push the first k elements into the return linked list and when we encounter the next element during traversal, just check if it is closer than the first element in the list. If yes, remove first and add this node val.

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            LinkedList<Integer> ret = new LinkedList<Integer>();
            
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curr = root;
            
            while(curr != null || !stack.isEmpty()) {
                if(curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                } else {
                    TreeNode top = stack.pop();
                    // push the first k elements to list
                    if(k > 0) {
                        ret.add(top.val);
                        k--;
                    } else if (k == 0) {
                        // When we have sufficient number of
                        // values in the list, compare the first
                        // value with the current treenode value,
                        // if it is less than the first one, remove
                        // first and add this node
                        int first = ret.getFirst();
                        if(Math.abs(target - top.val) < Math.abs(target - first)) {
                            ret.removeFirst();
                            ret.add(top.val);
                        } else {
                            // If this node val is greater than the current
                            // k closest values, then there is no point
                            // in iterating the BST further as we are doing
                            // inorder traversal.
                            break;
                        }
                    }
                    curr = top.right;
                }
            }
            
            return ret;
        }
    

Log in to reply
 

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