5ms JAVA O(logn) code following hint...


  • 0
    D
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        int k;
        double target, delta;
        List<Integer> result;
        Stack<TreeNode> pre, suc, stack;
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            result = new ArrayList<Integer>(k);
            if (root == null || k==0) return result;
            this.target = target;
            this.k=k;
            delta = Double.MAX_VALUE;
            stack = new Stack<TreeNode>();
            findClosestAndSolve(root);
            return result;
        }
        private boolean findClosestAndSolve(TreeNode node){
            boolean isCandidate = false, isWithinChildren= false;
            double curDelta = Math.abs(node.val-target);
            if (curDelta==0) {
                addResult(node);
                return true;
            }
            if (curDelta < delta) {
                delta = curDelta;
                isCandidate = true;
            }
            stack.push(node);
            if (node.val < target && node.right!=null) isWithinChildren = findClosestAndSolve(node.right);
            if (node.val > target && node.left !=null) isWithinChildren = findClosestAndSolve(node.left);
            stack.pop();
            if (isCandidate && !isWithinChildren) addResult(node);
            return isCandidate || isWithinChildren;
        }
        private void addResult(TreeNode node) {
            pre = (Stack<TreeNode>)stack.clone();
            suc = (Stack<TreeNode>)stack.clone();
            result.add(node.val);
            TreeNode p=getPredecessor(node), s=getSuccessor(node);
            while(result.size()<k) {
                if (p!=null) {
                    if (s==null || Math.abs(p.val-target) < Math.abs(s.val-target)) {
                        result.add(p.val);
                        p = getPredecessor(p);
                    } else {
                        result.add(s.val);
                        s = getSuccessor(s);
                    }
                } else if (s!=null) {
                    result.add(s.val);
                    s = getSuccessor(s);
                } else {
                    break;
                }
            }
        }
        private TreeNode getPredecessor(TreeNode node) {
            if (node.left!=null) {
                TreeNode left = node.left;
                while (left.right!=null) {
                    pre.push(left);
                    left = left.right;
                }
                return left;
            }
            while (!pre.empty()) {
                TreeNode top = pre.pop();
                if (top.val<=node.val) return top;
            }
            return null;
        }
        private TreeNode getSuccessor(TreeNode node) {
            if (node.right!=null) {
                TreeNode right = node.right;
                while (right.left!=null) {
                    suc.push(right);
                    right = right.left;
                }
                return right;
            }
            while (!suc.empty()){
                TreeNode top = suc.pop();
                if (top.val>=node.val) return top;
            }
            return null;
        }
    }
    

Log in to reply
 

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