[phone] given x, 找BST中比x大的immediate next (x’s ceiling)
Posted August 24, 2013
on:- 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; } }
Leave a Reply