Write an iterative method that finds depth of a (non-balanced) binary tree. - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Write an iterative method that finds depth of a (non-balanced) binary tree.

Write an iterative method that finds depth of a (non-balanced) binary tree.# JobHunting - 待字闺中

I*A2010-07-29 07:07

1 楼

anyone has written it?

z*n2010-07-29 07:07

2 楼

我觉得可以这样做
用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度

【在 I**A 的大作中提到】

: anyone has written it?

z*n2010-07-29 07:07

3 楼

好像不对，碰到右边叶子的时候，对应的根节点已经弹出了

【在 z****n 的大作中提到】

: 我觉得可以这样做
: 用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
: 素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
: 剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度

z*n2010-07-29 07:07

4 楼

改成用non-recursive的后序遍历就对了

【在 z****n 的大作中提到】

: 好像不对，碰到右边叶子的时候，对应的根节点已经弹出了

z*n2010-07-29 07:07

5 楼

代码
int maxPath = 0;
s.push(root);
while(!s.empty)
{
Node* n = s.peek();
if(n->left!=null&&!n->left->visited)
s.push(n->left);
else
{
if(n->right!=null&&!n->right->visited)
s.push(n->right)
else
{
Visit(n);
n->visited=true;
/* calculating path length */
if(n->left==null&&n->right==null) //leaf
{
int path = s.size();
if(path>

【在 z****n 的大作中提到】

: 改成用non-recursive的后序遍历就对了

I*A2010-07-29 07:07

6 楼

多谢～～～
我觉得这个思路是对的
有人有反对意见没？

【在 z****n 的大作中提到】

: 改成用non-recursive的后序遍历就对了