使用非遞歸后續(xù)遍歷：
#include<iostream>
#include<stack>
#include<map>
using namespace std;
struct Node
{
int v;
Node *lchild;
Node *rchild;
};
struct StackNode
{
Node *ptr;
int flag;
};
int maxDepth(Node *root)
{
stack<StackNode> s;
StackNode x;
Node *p = root;
int max = 0;
while (p || !s.empty())
{
while (p)
{
x.ptr = p;
x.flag = 0;
s.push(x);
if (s.size() > max)
max = s.size();
p = p->lchild;
}
while (!s.empty() && s.top().flag)
{
s.pop();
}
if (!s.empty())
{
s.top().flag = 1;
p = s.top().ptr->rchild;
}
}
return max;
}
int main()
{
int i, j;
map<int, Node*> m;
int a[][3] = {
{1,2,3},
{2,4,5},
{3,6,7},
{4,-1,-1},
{5,-1,-1},
{6,8,-1},
{7,-1,9},
{8,-1,-1},
{9,-1,10},
{10,-1,-1},
-1
};
for (i=0; a[i][0]!=-1; i++) {
Node *n = new Node;
n->v = a[i][0];
m[n->v] = n;
}
for (i=0; a[i][0]!=-1; i++) {
int s = a[i][0];
int l = a[i][1];
int r = a[i][2];
Node *n = m[s];
n->lchild = (l==-1 ? NULL : m[l]);
n->rchild = (r==-1 ? NULL : m[r]);
}
Node *root = m[a[0][0]];
cout << maxDepth(root) << endl;
return 0;
}