[Locked] Closest Binary Search Tree Value & Closest Binary Search Tree Value II

Closest Binary Search Tree Value 

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

Note:

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.

分析:

  按照正常的搜索路径,直到搜索到叶节点,选出在这个路径上离target最近的值返回

代码:

void dfs(TreeNode *cur, int &cv, double target) {
if(!cur)
return;
double num = double(cur->val) - target;
if(abs(num) < abs(double(cv) - target))
cv = cur->val;
if(num > )
dfs(cur->left, cv, target);
else
dfs(cur->right, cv, target);
return;
}

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.

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

Hint:

    1. 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.
    2. Try to assume that each node has a parent pointer, it makes the problem much easier.
    3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
    4. You would need two stacks to track the path in finding predecessor and successor node separately.
上一篇:深度学习论文翻译解析(八):Rich feature hierarchies for accurate object detection and semantic segmentation


下一篇:jQuery 插件开发文章收集