題目描述：
給定一顆二叉樹，使用非遞歸方法實(shí)現(xiàn)二叉樹的中序遍歷
- 題目來源：
- http://oj.leetcode.com/problems/binary-tree-inorder-traversal/
- 題目分析：
- 遞歸到非遞歸的轉(zhuǎn)換。使用棧描述遞歸的調(diào)用過程， while循環(huán)體計(jì)算遞歸程序的計(jì)算部分 。因?yàn)槊看蝫hile循環(huán)只能處理一次遞歸調(diào)用， 使用標(biāo)記記錄棧中節(jié)點(diǎn)的計(jì)算痕跡 ，例如：用tag記錄當(dāng)前根的調(diào)用記錄，當(dāng)根的左右子樹均未調(diào)用時(shí)，令tag值為0，當(dāng)根的左子樹已經(jīng)調(diào)用過時(shí)，令tag值為1。
- 時(shí)間復(fù)雜度： O（n） n為節(jié)點(diǎn)數(shù)
- 示例代碼：
vector<
int
> inorderTraversal(TreeNode *
root) {
stack
<TreeNode*>
stnode;
stack
<
char
>
sttag;
vector
<
int
>
result;
if
(root ==
NULL)
return
result;
stnode.push(root);
sttag.push(
'
0
'
);
while
(!
stnode.empty()) {
TreeNode
* topnode =
stnode.top();
char
toptag =
sttag.top();
if
(toptag ==
'
0
'
) {
sttag.pop();
sttag.push(
'
1
'
);
if
(topnode->left !=
NULL) {
stnode.push(topnode
->
left);
sttag.push(
'
0
'
);
}
}
else
if
(toptag ==
'
1
'
) {
result.push_back(topnode
->
val);
stnode.pop();
sttag.pop();
if
(topnode->right !=
NULL) {
stnode.push(topnode
->
right);
sttag.push(
'
0
'
);
}
}
}
return
result;
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
