[phone] find the node that value is closest to x in BST

Posted by: lexigrey on: August 28, 2013

• In: 面经
• Leave a Comment

对这类题型其实不够熟悉，写了有15分钟才出来，太差了。总结一下。

BST一般找不到就null了，没办法keep track of走到哪个位置的信息。所以多传两个参数，leftBoundary和rightBoundary，分别表示“当前node为root的子树的left boundary – 当前子树的immediate prev）“和“immediate next”。因为你是top down的往下算，所以左右两边的boundary不断narrow down。当node == null时，此时的最靠近自己的boundary就起作用了，找他们之间最接近x的就行了。

这题和判断一棵树是不是BST是一个套路（后面有对比）：

public TreeNode getClosest(TreeNode node, TreeNode leftBoundary, TreeNode rightBoundary, int x) {
  if (node == null)
    return getClosest(leftBoundary, rightBoundary, x);
  if (node.val < x) {
    return getClosest(node.right, node, rightBoundary, x);
  } else {
    return getClosest(node.left, leftBoundary, node, x);
  }
}
private TreeNode getClosest(TreeNode prev, TreeNode next, int x) {
  if (prev == null || next == null)
    return prev == null ? next : prev;
  if (next.val - x < x - prev.val)
    return next;
  else
    return prev;
}

附加：判断一棵树是不是BST，也是一路传下来boundary，不断看当前节点是不是满足上面传下来的左右boundary， 然后往下传的时候narrow down。最开始left, right, node都是null（没有左右节点限制）。

boolean isBST(Node node, Node leftBoundary, Node rightBoundary) {
  if (node == null)
    return true;
  if ((leftBoundary != null && node.val < leftBoundary.val) || (rightBoundary != null && node.val > rightBoundary.val))
    return false;
  if (!isBST(node.left, leftBoundary, node))
    return is BST(node.right, node, rightBoundary);
}

Tags: BST, tree, 前序, 固定解法