這里假定每棵樹都是完美二叉樹
思路:
首先驗(yàn)證是否存在當(dāng)前節(jié)點(diǎn),以及當(dāng)前節(jié)點(diǎn)的左子節(jié).
從當(dāng)前層操作下一層,外層循環(huán)每次一都使層次下降一層,并使當(dāng)前節(jié)點(diǎn)為當(dāng)前層次最左端.
內(nèi)層循環(huán)從最左端節(jié)點(diǎn)開始,用next每次循環(huán)向右移動(dòng)一個(gè)節(jié)點(diǎn),直到null.
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
while root and root.left:
next = root.left
while root:
root.left.next = root.right
root.right.next = root.next and root.next.left
root = root.next
root = next
注意,python中的and從左到右計(jì)算表達(dá)式，若所有值均為真，則返回最后一個(gè)值始鱼，若存在假仔掸，返回第一個(gè)假值。
or也是從左到右計(jì)算表達(dá)式医清，返回第一個(gè)為真的值,若都為假,返回最后一個(gè)假值.
117.假定給的樹為任意二叉樹
那么上面的策略就不能用了,因?yàn)椴荒鼙ＷC最左端始終有節(jié)點(diǎn).
這次的思路是:
引入兩個(gè)節(jié)點(diǎn)prekid = kid = TreeLinkNode(0)
每層都開始于一個(gè)dummy node prekid
root在當(dāng)前層,kid在下一層,
prekid.next是下一層的頭結(jié)點(diǎn)
內(nèi)層循環(huán)結(jié)束時(shí),root, kid = prekid.next, prekid
把root變成下層的頭結(jié)點(diǎn),kid重新變?yōu)閐ummy node
def connect(self, root):
prekid = kid = TreeLinkNode(0)
while root:
while root:
kid.next = root.left
kid = kid.next or kid
kid.next = root.right
kid = kid.next or kid
root = root.next
root, kid = prekid.next, prekid
