原題
給定一個(gè)二叉樹
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)涝影。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL阳藻。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL谈撒。
說明:
你只能使用額外常數(shù)空間腥泥。
使用遞歸解題也符合要求，本題中遞歸程序占用的椏心洌空間不算做額外的空間復(fù)雜度蛔外。
你可以假設(shè)它是一個(gè)完美二叉樹（即所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)）溯乒。
示例:
給定完美二叉樹夹厌，
1 / \ 2 3 / \ / \ 4 5 6 7
調(diào)用你的函數(shù)后，該完美二叉樹變?yōu)椋?/p>
1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL
思路
由于題目中常數(shù)空間的限制裆悄，采用隊(duì)列的方式對樹進(jìn)行層次遍歷是不可行的尊流。
若把問題轉(zhuǎn)化為給定一層已經(jīng)鏈接的節(jié)點(diǎn)，請鏈接下面一層灯帮，這樣問題就迎刃而解了崖技。用start記錄當(dāng)前層的第一個(gè)節(jié)點(diǎn)，再用cur循環(huán)當(dāng)前層的每個(gè)節(jié)點(diǎn)钟哥。若cur.left存在迎献，則鏈接cur.left和cur.right；若cur.next存在腻贰，則鏈接cur.right和cur.next.left吁恍。下一層的首個(gè)節(jié)點(diǎn)即start.left，如此循環(huán)播演。
按此思路冀瓦，代碼也就很簡單了。
代碼
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
start = root
while start:
cur = start
while cur and cur.left:
cur.left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next
start = start.left
