標籤：

c++ 二叉樹的中序遍歷（非遞歸實現）是哪裡出錯了？

01-11

代碼如下：編譯沒有問題，執行或者調試的時候會報錯誤。我的編譯環境是GCC

#include &
#include &
#include &

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

vector& inorderTraversal(TreeNode* root) {
vector& ans;
stack& s;
if(!root) {
return ans;
}
while(root || !s.empty()) {
while(root) {
s.push(root);
root = root-&>left;
}
if(!s.empty()) {
ans.push_back(root-&>val);
root = s.top()-&>right;
s.pop();
}
}
return ans;
}

int main()
{
TreeNode *node = new TreeNode(1);
vector& ans = inorderTraversal(node);

for(auto a : ans) {
cout &<&< a &<&

while(root) {
s.push(root);
root = root-&>left;
}
if(!s.empty()) {
ans.push_back(root-&>val);
root = s.top()-&>right;
s.pop();
}

代碼邏輯有問題呀，前一個while跑完root就是空的，後面root-&>val肯定會報錯。正確的應該是這樣

if (!s.empty())
{
root = s.top();
s.pop();
ans.push_back(root-&>val);
root = root-&>right;
}

推薦閱讀：

※客戶端產品迭代周期為多長時間比較合適?

TAG:C | 迭代 | 二叉樹 |