Leetcode solution 272: Closest Binary

包子面试培训

发布于 2019-06-03 15:01:51

5950

发布于 2019-06-03 15:01:51

文章被收录于专栏：包子铺里聊IT

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-05-17，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js

编程算法

本文分享自包子铺里聊IT 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

node.js

编程算法

登录后参与评论

0 条评论

热度