r****o
发帖数: 1950 | 1 非递归求二叉树的高度，可以用按层次遍历的方法，层数就是高度。
还有其他方法可以非递归求二叉树高度吗? |
f*******e
发帖数: 1161 | 2 节点加一个data field: depth
【在 r****o 的大作中提到】
: 非递归求二叉树的高度，可以用按层次遍历的方法，层数就是高度。
: 还有其他方法可以非递归求二叉树高度吗?
|
r****o
发帖数: 1950 | 3 然后pre-order遍历？
如果不改动节点数据结构的话，有什么方法可行吗?
【在 f*******e 的大作中提到】
: 节点加一个data field: depth
|
d*****a
发帖数: 38 | 4 这应该和如何遍历没关系，总之就是遍历所有叶结点才能得到深度。 |
r****o
发帖数: 1950 | 5 好吧，能不能具体说说怎么弄呢? 如果不改变节点数据结构的话。
【在 d*****a 的大作中提到】
: 这应该和如何遍历没关系，总之就是遍历所有叶结点才能得到深度。
|
m*****g
发帖数: 226 | 6 int treeDepthNonRec(treeNode *root)
{
int maxDepth = 0;
if(!root) return 0;
stack > treeNodeStack;
//using traversal
treeNodeStack.push(make_pair(root, root->numChildren));
int depth = 0;
while(!treeNodeStack.empty())
{
pair curNode = treeNodeStack.top();
treeNodeStack.pop();
if(curNode.second)
{
treeNode *curChild = curNode.first->children[curNode.second-1];
|
r****o
发帖数: 1950 | 7 多谢！
【在 m*****g 的大作中提到】
: int treeDepthNonRec(treeNode *root)
: {
: int maxDepth = 0;
: if(!root) return 0;
: stack > treeNodeStack;
: //using traversal
: treeNodeStack.push(make_pair(root, root->numChildren));
:
: int depth = 0;
: while(!treeNodeStack.empty())
|
h****8
发帖数: 599 | 8 请教一下 有个地方没看懂
if(curNode.second)
{
treeNode *curChild = curNode.first->children[curNode.second-1];
treeNodeStack.push(make_pair(curNode.first, curNode.second-1));
treeNodeStack.push(make_pair(curChild, curChild->numChildren));
}
else
{
if(!(curNode.first->numChildren)) //leaf node
{
depth = 0;
}
else
这里最后一个else是什么情况？哪些情况才会depth++?
【在 m*****g 的大作中提到】
: int treeDepthNonRec(treeNode *root)
: {
: int maxDepth = 0;
: if(!root) return 0;
: stack > treeNodeStack;
: //using traversal
: treeNodeStack.push(make_pair(root, root->numChildren));
:
: int depth = 0;
: while(!treeNodeStack.empty())
|
