Binary Tree Inorder Traversal -- leetcode

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

實(shí)現(xiàn)中序遍歷，且不能用遞歸。

算法1：使用棧

中序遍歷為，先訪問(wèn)左子樹(shù)，再訪問(wèn)根。

訪問(wèn)完左子樹(shù)，需要要回到根。而樹(shù)本身并沒(méi)有存儲(chǔ)到根的指針。

故需要棧的幫助，存儲(chǔ)指向父結(jié)點(diǎn)的指針。即先把自己入棧，再進(jìn)入左子樹(shù)。

此代碼在leetcode上，實(shí)際履行時(shí)間為5ms。

利用空閑的right指針指向根結(jié)點(diǎn)。這樣在訪問(wèn)完左子樹(shù)時(shí)，根據(jù)右孩子，回到根結(jié)點(diǎn)。

中序遍歷，要求，先訪問(wèn)左子樹(shù)的所有結(jié)點(diǎn)，然后訪問(wèn)該結(jié)點(diǎn)。

那末根結(jié)點(diǎn)root的左子樹(shù)中最右下的結(jié)點(diǎn)rightMost必為左子樹(shù)最后1個(gè)被訪問(wèn)的結(jié)點(diǎn)。而此結(jié)點(diǎn)rightMost的右指針，必為空。  則可以復(fù)用此右指針，指向根結(jié)點(diǎn)root。 這樣，在訪問(wèn)完rightMost后，就能夠回到根結(jié)點(diǎn)root了。

故，在進(jìn)入左子樹(shù)之前，先找到左子樹(shù)中最右下的結(jié)點(diǎn)，讓其right指針，指向自己。未思進(jìn)，先思退。留好退路。

這樣，rigth指針就有2義性，即表示右子樹(shù)，又表示先人結(jié)點(diǎn)。如何避免2義性呢，同時(shí)也為了不死循環(huán)。

那就是，在尋覓其左子樹(shù)的最右下結(jié)點(diǎn)時(shí)，如果又回到了自己。說(shuō)明它左子樹(shù)，已全部訪問(wèn)完成。

即，尋覓最右結(jié)點(diǎn)時(shí)，會(huì)出現(xiàn)兩種情況，1種是碰到right為空；1種是回到了自己。

此代碼在leetcode上實(shí)際履行時(shí)間為4ms。

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)