Given BST, using in-order traversal!


  • 2
    L

    The key of thinking this question is based on BST. If we in-order traverse the whole tree, the number in each tree go in ascending order, in this way we can change this question into an ascending order array.

    For example, given [2,3,4,5,6,7,8], find k = 3, target = 7.5 ? Which is easy!

    You have a linked-list first, and if the length of linked-list < k, you can add value into it without hesitation,
    so for first three elements, the linked-list changes like
    [2] -> [2,3] -> [2,3,4]

    And when you meet one more element, we have to remove one, but which one?
    Also easy.

    1. If the one we meet is less than target, we just remove the head of linked-list
    2. If the one we meet is larger than the target, we decide to move the head of linked-list if it is farther to target. Furthermore if the one we meet is farther than the head of linked-list from target, we do not have to go in the array anymore because next element will be farther!

    so the linked list change like:
    [2,3,4] -> [3,4,5] -> [4,5,6] -> [5,6,7] -> [7,8,9]

    public class Solution {
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            List<Integer> ret = new LinkedList<>();
            
            if(root == null) return ret;
            
            helper(root, ret, target, k);
            
            return ret;
        }
        // in order traversal保证遍历的数是增序的
        private void helper(TreeNode root, List<Integer> list, double target, int k){
            if(root == null) return;
            
            helper(root.left, list, target, k);
            
            if(list.size() < k){
                // 如果list里面的数量还不到K,可以直接放进去等待以后处理
                list.add(root.val);
            }else{
                // 如果list已经满了,且当前的数小于target,
                // 因为前序遍历的数是增序的,这个当前数肯定比list里面最前面的数
                // 接近target
                if(root.val <= target){
                    list.remove(0);
                    list.add(root.val);
                }else{
                    // 如果这个当前的数大于target, 且距离list里面最小的数相对target的距离更大
                    // 就可以不用再往后搜了,因为后面的数还是增序的
                    
                    if(Math.abs(list.get(0) - target) > Math.abs(root.val - target)){
                        list.remove(0);
                        list.add(root.val);
                    }else{
                        return;
                    }
                }
            }
            
            helper(root.right, list, target, k);
        }
    }

  • 0
    S

    Is this algorithm has O(n) time complexity? The task was to solve the problem faster.


  • 0
    L

    I think it is worst case is O(n). The worst case will be in in-order traverse, the last k nodes are nearest k nodes. In this case you have to traverse all nodes in tree.


Log in to reply
 

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