I**A
发帖数: 2345 | |
z****n
发帖数: 1379 | 2 我觉得可以这样做
用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度
【在 I**A 的大作中提到】
: anyone has written it?
|
z****n
发帖数: 1379 | 3 好像不对，碰到右边叶子的时候，对应的根节点已经弹出了
【在 z****n 的大作中提到】
: 我觉得可以这样做
: 用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
: 素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
: 剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度
|
z****n
发帖数: 1379 | 4 改成用non-recursive的后序遍历就对了
【在 z****n 的大作中提到】
: 好像不对，碰到右边叶子的时候，对应的根节点已经弹出了
|
z****n
发帖数: 1379 | 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**A
发帖数: 2345 | 6 多谢～～～
我觉得这个思路是对的
有人有反对意见没？
【在 z****n 的大作中提到】
: 改成用non-recursive的后序遍历就对了
|
h**6
发帖数: 4160 | 7 non-recursive的BFS最简单，数一数有多少行就行了。 |
I**A
发帖数: 2345 | 8 啊，也对, this logic is easier to understand..
i like queue better than stack
//鄙视自己，简直是随风倒。。
【在 h**6 的大作中提到】
: non-recursive的BFS最简单，数一数有多少行就行了。
|
p*u
发帖数: 136 | 9 同意
正打算建议用BFS
【在 h**6 的大作中提到】
: non-recursive的BFS最简单，数一数有多少行就行了。
|
