Leetcode solution 272: Closest Binary

https://blog.baozitraining.org/2019/05/leetcode-solution-272-closest-binary.html

请点击阅读原文

Problem Statement

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hints

  • Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  • Try to assume that each node has a parent pointer, it makes the problem much easier.
  • Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  • You would need two stacks to track the path in finding predecessor and successor node separately.

Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

At first glance, it might look very similar to the Closest Binary Search Tree Value. They need look similar except finding K in less than O(N) time is way harder, hehehehe Okay, more seriously.

Brute force, convert BST into sorted array

A quick thought would be if we traverse the BST in order, and put them into an array, now the problem becomes given an sorted array, find K elements that are closest to the target. That search should be done binary search find the target, and expand left and right compare the values with diff, take the smaller one and continue. Overall, this brute force idea time complexity would be O(N), and space complexity is O(N), N is the total number of tree nodes.

Use a max heap

Another way or anytime when you need to find K things, always think about heap. Here if we traverse the tree (in any order) and use a K sized max heap, we can solve the problem in O(NlgK) time complexity, O(K) space complexity

Use two stacks

This is a smart idea that I read from leetcode discussion. This is also following leetcode's hint. Keeping two separate stacks, one stack is all the nodes less or equal to the target (i.e., predecessor), the other is all the nodes larger than the target (i.e., successor). After that, merge those two stacks and keep the K closest element to target. Note, the time complexity is still O(N + K). Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.

Use threaded tree

You might also think about the double threaded tree given the hint, starting from the root, keep asking the predecessor and successor since double threaded tree allows you to have that. However, I didn't code this one up since it requires you to modify the tree structure which normally not allowed in interviews and also it's a bit too complicated for a coding interview

Solutions

Brute force, convert BST into sorted array

Code it on your own :) Time Complexity: assuming tree size is N, O(N) Space Complexity: O(N)

Use a max heap

public List<Integer> closestKValuesUsingPreOrder(TreeNode root, double target, int k) {

List<Integer> res = new ArrayList<>();

// PQ by default is ascending order using the element's natural order, so by default, it's a min heap

Queue<Node> pq = new PriorityQueue<>(); // max heap

this.preOrderTraversal(root, target, pq, k);

for (Node n : pq) {

res.add(n.val);

}

return res;

}

// This method uses a pre-order traversal that traverses the entire tree, O(N*lgK), not optimal

public void preOrderTraversal(TreeNode root, double target, Queue<Node> pq, int k) {

if (root == null) {

return;

}

if (pq.size() < k) {

pq.add(new Node(root.val, Math.abs(target - root.val)));

} else {

double diff = Math.abs(target - root.val);

if (diff < pq.peek().diff) {

pq.poll();

pq.add(new Node(root.val, diff));

}

}

this.preOrderTraversal(root.left, target, pq, k);

this.preOrderTraversal(root.right, target, pq, k);

}

public class Node implements Comparable {

public int val;

public double diff;

public Node(int val, double diff) {

this.val = val;

this.diff = diff;

}

// Want to build a max heap

public int compareTo(Object o) {

Node n = (Node)o;

return (int)(n.diff - this.diff);

}

}

view rawCloestBinarySearchTreeValueIIPreorder.java hosted with ❤ by GitHub

Time Complexity: assuming tree size is N, O(NlgK) because insertion into PQ is O(lgK) Space Complexity: O(K)

Use two stacks

/**

this method is also worst case O(N), however, if BST is balanced, this would be O(K + lgN)

*/

public List<Integer> closestKValues(TreeNode root, double target, int k) {

List<Integer> res = new ArrayList<>();

Stack<Integer> predecessors = new Stack<>();

Stack<Integer> successors = new Stack<>();

this.traverseTreeInorder(root, target, predecessors);

this.traverseTreeReverseInorder(root, target, successors);

while (k > 0) {

if (predecessors.empty()) {

res.add(successors.pop());

} else if (successors.empty()) {

res.add(predecessors.pop());

} else if (Math.abs(predecessors.peek() - target) < Math.abs(successors.peek() - target)) {

res.add(predecessors.pop());

} else {

res.add(successors.pop());

}

k--;

}

return res;

}

private void traverseTreeInorder(TreeNode node, double target, Stack<Integer> predecessor) {

if (node == null) {

return;

}

this.traverseTreeInorder(node.left, target, predecessor);

// have to exclude at least once from either methods traverseTreeInorder or traverseTreeReverseInorder to avoid

// duplicates

if (node.val >= target) {

return;

}

predecessor.push(node.val);

this.traverseTreeInorder(node.right, target, predecessor);

}

private void traverseTreeReverseInorder(TreeNode node, double target, Stack<Integer> successor) {

if (node == null) {

return;

}

this.traverseTreeReverseInorder(node.right, target, successor);

if (node.val < target) {

return;

}

successor.push(node.val);

this.traverseTreeReverseInorder(node.left, target, successor);

}

view rawCloestBinarySearchTreeValueIIUseTwoStacks.java hosted with ❤ by GitHub

Time Complexity: assuming tree size is N, O(N+K) worst case. Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree. Space Complexity: O(N) worst case. Even if BST is balanced, we still need O(N/2), still O(N)

References

  • Leetcode discussion solution using two stacks

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2019-05-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券