題目描述：
給定一顆二叉樹，使用非遞歸方法實現(xiàn)二叉樹的中序遍歷
- 題目來源：
- http://oj.leetcode.com/problems/binary-tree-inorder-traversal/
- 題目分析：
- 遞歸到非遞歸的轉(zhuǎn)換。使用棧描述遞歸的調(diào)用過程， while循環(huán)體計算遞歸程序的計算部分 。因為每次while循環(huán)只能處理一次遞歸調(diào)用， 使用標記記錄棧中節(jié)點的計算痕跡 ，例如：用tag記錄當前根的調(diào)用記錄，當根的左右子樹均未調(diào)用時，令tag值為0，當根的左子樹已經(jīng)調(diào)用過時，令tag值為1。
- 時間復雜度： O（n） n為節(jié)點數(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;
}
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
