<p>下面的代码很容易记住,因为我们只需更改(3行代码)</strong>,<em><strong>左根右键的顺序,就像我们使用<em><strong>递归时所做的那样</p>
<p>这个问题是关于Python实现的,但由于数据结构是独立于语言的,所以我发布这个答案是为了让其他人受益</p>
<p>它是<strong>O(N)</strong>空间,使用<strong>单堆栈</strong>和<strong>无递归</strong></p>
<p>对于<strong><strong>顺序遍历</strong></strong></p>
<pre><code>#include <bits/stdc++.h>
using namespace std;
struct node{
int val;
node *left, *right;
node(int x) {
val = x;
left = right = NULL;
}
};
void traversal_trick(node *root) {
//inorder
stack<pair<node*, int>> S;
S.push({root, 0});
while(!S.empty()){
pair<node*, int> t = S.top();
node* cur = t.first;
int state = t.second;
S.pop();
if(cur == NULL or state == 3) continue;
S.push({cur, state+1});
if (state == 0) S.push({cur->left, 0});
else if (state == 1) cout << cur->val << " " ;
else if (state == 2) S.push({cur->right, 0});
}
}
int main()
{
node *root = new node(7);
node *t = root;
root->left = new node(3); root->right = new node(10);
root->left->left = new node(2); root->left->right = new node(5);
root->left->left->left = new node(1);
root->right->left = new node(8);
root->right->right = new node(12);
traversal_trick(root);
}
</code></pre>
<p>对于<strong>前序遍历</strong>:只需更改这部分代码</p>
<pre><code> if (state == 0) cout << cur->val << " " ;
else if (state == 1) S.push({cur->left, 0});
else if (state == 2) S.push({cur->right, 0});
</code></pre>
<p>对于<strong>后序遍历</strong>:只需更改这部分代码即可</p>
<pre><code> if (state == 0) S.push({cur->left, 0}) ;
else if (state == 1) S.push({cur->right, 0}) ;
else if (state == 2) cout << cur->val << " ";
</code></pre>
<p>解释见<a href="https://youtu.be/5BzvEmscu-o" rel="nofollow noreferrer">this</a></p>