Archive for August 28th, 2013
- In: 面经
- Leave a Comment
别用傻乎乎的additional data structure，那样可以做，但是写起来太长。这个题上来的思路就是用左中右的inorder，这样一路下来，prev.next = curr，不断update当前的node为prev。但是写了半天，不知道怎么传prev，因为担心传java reference的问题；又回到了那个IntWrapper tree serialization的题。都是一个类型:https://leetcodenotes.wordpress.com/2013/08/24/phone-serializede-serialize-a-tree/
public void addSuccessor(Node node, Node[] prev) {
if (node == null)
return;
addSuccessor(node.left, prev);
if (prev[0] != null)
prev[0].next = node;
prev[0] = node;
addSuccessor(node.right, prev);
}
类似题：找tree的in order traversal第x个节点：keep一个current node的index counter，同样是inorder的pattern，到当前node的时候counter++。这个init的i应该是-1，因为第一次找到最左边的节点的时候，i先+1，然后和x比较。
public TreeNode getNthNode(TreeNode node, IntWrapper i, int x) {
if (node == null)
return null;
TreeNode foundAtLeft = getNthNode(node.left, i, x);
i.val++;
if (i.val == x)
return node;
if (foundAtLeft != null)
return foundAtLeft;
return getNthNode(node.right, i, x);
}
- 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);
}
Lexi's Leetcode solutions 