Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL
For example,
Given the following perfect binary tree,
1
/
2 3
/ \ /
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/
2 -> 3 -> NULL
/ \ /
4->5->6->7 -> NULL
這題我一開(kāi)始想用queue那套來(lái)做發(fā)現(xiàn)比較難。然后看了leetcode里面一個(gè)人的答案簇秒，感覺(jué)非常tricky鱼喉。。簡(jiǎn)單說(shuō)就是cur在本層向右走，pre向下一層的第一個(gè)node走扛禽。尤其那句:cur.right.next = cur.next.left;锋边，需要畫(huà)個(gè)圖來(lái)看會(huì)比較清楚。還有兩層while的條件也很巧妙编曼。
這種題好像沒(méi)有套路可尋豆巨，感覺(jué)不太好在面試的時(shí)候想到這樣的解法。
public void connect(TreeLinkNode root) {
if (root == null) return;
TreeLinkNode pre = root;
TreeLinkNode cur = null;
while (pre.left != null) {
cur = pre;
while (cur != null) {
//pre.left!=null保證了cur.left不為Null
cur.left.next = cur.right;
//無(wú)形中把下一層的最左邊的node跟右邊連接起來(lái)了
if (cur.next != null) {
cur.right.next = cur.next.left;
}
cur = cur.next;
}
pre = pre.left;
}
}
