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.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * public int val;
5 * public TreeNode left;
6 * public TreeNode right;
7 * public TreeNode(int x) { val = x; }
8 * }
9 */
10 public class Solution {
11 public IList<int> ClosestKValues(TreeNode root, double target, int k) {
12 var result = new List<int>();
13
14 Stack<int> s1 = new Stack<int>(), s2 = new Stack<int>();
15 Inorder(root, target, true, s1);
16 Inorder(root, target, false, s2);
17
18 for (int i = 0; i < k; i++)
19 {
20 if (s1.Count == 0)
21 {
22 result.Add(s2.Pop());
23 }
24 else if (s2.Count == 0)
25 {
26 result.Add(s1.Pop());
27 }
28 else
29 {
30 double d1 = Math.Abs((double)s1.Peek() - target);
31 double d2 = Math.Abs((double)s2.Peek() - target);
32
33 if (d1 < d2)
34 {
35 result.Add(s1.Pop());
36 }
37 else
38 {
39 result.Add(s2.Pop());
40 }
41 }
42 }
43
44 return result;
45 }
46
47
48 private void Inorder(TreeNode node, double target, bool reverse, Stack<int> stack)
49 {
50 if (node == null) return;
51
52 Inorder(reverse ? node.right : node.left, target, reverse, stack);
53
54 if (reverse ? (double)node.val <= target : (double)node.val > target)
55 {
56 return;
57 }
58
59 stack.Push(node.val);
60
61 Inorder(reverse ? node.left : node.right, target, reverse, stack);
62 }
63 }
轉載于:https://www.cnblogs.com/liangmou/p/8071212.html