LeetCode 272 Closest Binary Search Tree Value II

LeetCode 272 Closest Binary Search Tree Value II

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)?

题目大意：

找BST中给定目标的最接近的k个值。

解题思路：

首先观察得到最接近的节点一定在二叉树的搜索路径上的节点的其中一个。这样可以分成两组
前驱节点和后驱节点（比target大），加入到两个stack中，由BST的iterator可以知道这两个
stack的越靠近栈首就越接近target，所以出栈的一定是最接近target的。只要比较两栈首元素
即可。如果某个节点出栈要找其儿子节点填充。找前驱节点和后驱节点的方法是相反的。这里可
参照KB的BST非递归中序遍历。

注意事项：

1. 找最接近target的节点，不用判断左右儿子是否为空，因为若为空，表示root更接近。大于target的放入successors，否则是predecessors
2. 然后判断两栈首谁大，谁大的就获得相应的比它远离target的节点入栈。如predecessors是左节点的所有右儿子。

Python代码：

def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
	predecessors, successors = [], []
	it = root
	while it:
		if target < it.val:
			successors.append(it)
			it = it.left
		else:
			predecessors.append(it)
			it = it.right
	res = []
	while k > 0:
		if predecessors and (not successors or target - predecessors[-1].val < successors[-1].val - target):
			node = predecessors.pop()
			if node.left:
				n = node.left
				while n:
					predecessors.append(n)
					n = n.right
			res.append(node.val)
		else:
			node = successors.pop()
			if node.right:
				n = node.right
				while n:
					successors.append(n)
					n = n.left
			res.append(node.val)
		k -= 1
	return res

注意事项：

1. target - preOrder.peek().val < postOrder.peek().val - target的条件前
   记得加上!preOrder.isEmpty()

Java代码：

public List<Integer> closestKValues(TreeNode root, double target, int k) {
	List<Integer> res = new ArrayList<>();
	if(root == null)
		return res;
	Stack<TreeNode> preOrder = new Stack<>();
	Stack<TreeNode> postOrder = new Stack<>();
	findTargetAndPopulateStacks(preOrder, postOrder, root, target);
	
	while(k-- > 0) {
		if(postOrder.isEmpty() || (!preOrder.isEmpty() && 
				target - preOrder.peek().val < postOrder.peek().val - target))
			getPredecessor(preOrder, res);
		else 
			getSuccessor(postOrder, res);
	}
	return res;
}

void findTargetAndPopulateStacks(Stack<TreeNode> preOrder, Stack<TreeNode> postOrder, 
		TreeNode root, double target) {
	TreeNode node = root;
	while(node != null) {
		if(node.val < target) { 
			preOrder.push(node);
			node = node.right;
		}
		else {
			postOrder.push(node);
			node = node.left;
		}
	}
}

void getSuccessor(Stack<TreeNode> postOrder, List<Integer> res) {
	TreeNode node = postOrder.pop();
	res.add(node.val);
	if(node.right != null) {
		TreeNode n = node.right;
		while(n != null) {
			postOrder.push(n);
			n = n.left;
		}
	}
}

void getPredecessor(Stack<TreeNode> preOrder, List<Integer> res) {
	TreeNode node = preOrder.pop();
	res.add(node.val);
	if(node.left != null) {
		TreeNode n = node.left;
		while(n != null) {
			preOrder.push(n);
			n = n.right;
		}
	}
}

算法分析：

时间复杂度为O(k + logn)，空间复杂度O(logn)。