[phone] 树populate 每个节点的successor pointer & 找tree的第x个节点
Posted August 28, 2013
on:- 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); }
Leave a Reply