Posts Tagged ‘中序’
- 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: leetcode
- 2 Comments
思路很straight forward，就是找到两个不属于自己位置的node，把他们的值互换。
但是怎么找这两个node就非常麻烦。怎么看出一个节点出位了？比如下图，能看出来是6出位了，但是1->6是满足的，6->3才发现不对劲。但也不能说prev > next就是prev不对，比如右边的5, 2，明明是2不对，但是2这个时候是后一个。所以总结来看，应该是“第一个不对劲的prev, curr pair是prev的错（不该跑前面的跑前面去了），第二个不对劲的prev, curr pair是curr的错（不该放后面的被放在了后面）。” 这个比较难想，总之就是中序遍历一遍，keep prev指针，按照刚说的规律找出那两个不对的。
5
/ \
3 8
/ \ / \
6 4 2 9
/
1
但是！！跑一遍不对！然后发现又是java不能改argument pointer的问题！栽在这上面两次了！！这回一定要弄清楚，记住教训！下面是错误版本：
private void populateMistakesArray(TreeNode[] mistakes, TreeNode root,TreeNode prev) { if (root == null) return; populateMistakesArray(mistakes, root.left, prev); if (prev != null && prev.val > root.val) { if (mistakes[0] == null) mistakes[0] = prev; mistakes[1] = root; }prev = root;populateMistakesArray(mistakes, root.right, prev); }
这样传prev进来，prev = root这一句，method 里面叫prev的variable point to root了，然后传给下一层没问题，但是没法传给上一层！因为毕竟改的是local var， 上一层prev还是以前那个prev！！以前一直这么写树的题都没问题，是因为parameter要么一路往下传，要么想往上传的话就作为return object往上传。这次坑爹的，想往上传还放paramter里，必须挂。解决方法：用一个array把prev包起来(TreeNode[] preWrapper)，就能真的改para的内容了(prevWrapper[0] = root)
keep in order traversal pointer是个固定trick，见https://leetcodenotes.wordpress.com/2013/08/28/phone-%E6%A0%91populate-%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84successor-pointer/
————————————————-10月份重做——————————————————
这个题第二遍做，又栽在一个trick里——如果swap的两个数正好在中序里面连着，那只能detect出来一次Out of order（比如1235467，发现5>4，然后mistake[0]放上5了，然后4<6，正常一路下去，mistake[1]永远也没被populate出来）。为了接住这个情况，在发现mistake[0]之后立刻把下一个当作mistake[1]赋上，要是后面真有mistake[1]，反正也会覆盖；要是后面没有，正好接住了上面说的特殊情况）。
Tree的test case:
Lexi's Leetcode solutions 