[phone] given x, 找BST中比x大的immediate next (x’s ceiling)

Posted by: lexigrey on: August 24, 2013

• In: 面经
• Leave a Comment

五分钟bug free，忍不住有成就感。

思路：root <= x，说明肯定不在左边，往右找；root >x，有可能是本身：如果root.left没找到，那就是本身了；如果找到了，那就返回找到那个。

public TreeNode getImmediateNext(TreeNode node, int x) {
  if (node == null)
    return null;
  if (node.val <= x) {
    return getImmediateNext(node.right, x);
  } else {
    TreeNode parent = node;
    TreeNode findAtLeft = getImmediateNext(node.left, x);
    return findAtLeft== null ? parent : findAtLeft;
  }
}

Tags: easy, tree