[phone] 树populate 每个节点的successor pointer & 找tree的第x个节点

Posted by: lexigrey on: August 28, 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);
}

Tags: tree, 固定解法, 中序