Write an iterative method that finds depth of a (non-balanced) binary tree.# JobHunting - 待字闺中
I*A
1 楼
anyone has written it?
z*n
2 楼
我觉得可以这样做
用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度
【在 I**A 的大作中提到】
: anyone has written it?
用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度
【在 I**A 的大作中提到】
: anyone has written it?
z*n
3 楼
好像不对，碰到右边叶子的时候，对应的根节点已经弹出了
【在 z****n 的大作中提到】
: 我觉得可以这样做
: 用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
: 素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
: 剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度
【在 z****n 的大作中提到】
: 我觉得可以这样做
: 用non-recursive的in-order遍历，每次碰到叶子节点，就数一下当前stack里有几个元
: 素，这就是这条路径的长度，（因为只有根节点入栈，左右孩子不入）
: 剩下就简单了，和当前最长路径比一下就行了，最后结束时的最长路径就是高度
z*n
4 楼
改成用non-recursive的后序遍历就对了
【在 z****n 的大作中提到】
: 好像不对，碰到右边叶子的时候，对应的根节点已经弹出了
【在 z****n 的大作中提到】
: 好像不对，碰到右边叶子的时候，对应的根节点已经弹出了
z*n
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的后序遍历就对了
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
6 楼
多谢～～～
我觉得这个思路是对的
有人有反对意见没？
【在 z****n 的大作中提到】
: 改成用non-recursive的后序遍历就对了
我觉得这个思路是对的
有人有反对意见没？
【在 z****n 的大作中提到】
: 改成用non-recursive的后序遍历就对了
h*6
7 楼
non-recursive的BFS最简单，数一数有多少行就行了。
I*A
8 楼
啊，也对, this logic is easier to understand..
i like queue better than stack
//鄙视自己，简直是随风倒。。
【在 h**6 的大作中提到】
: non-recursive的BFS最简单，数一数有多少行就行了。
i like queue better than stack
//鄙视自己，简直是随风倒。。
【在 h**6 的大作中提到】
: non-recursive的BFS最简单，数一数有多少行就行了。
p*u
9 楼
同意
正打算建议用BFS
【在 h**6 的大作中提到】
: non-recursive的BFS最简单，数一数有多少行就行了。
正打算建议用BFS
【在 h**6 的大作中提到】
: non-recursive的BFS最简单，数一数有多少行就行了。
相关阅读
可怕，那个年头待字闺中都犯法孙悟空要是放在现代，最受哪种职业欢迎？果家这种结果什么意思TRUMP要放大招封杀国内公司剽窃美国高科技新人磨三年？国外文化建设也还是那老三样一个生理期惊动bbc的女人Netflix怎么据人？挖坑，索男上blind吗？征九章算法团购 （真的不是广告贴）超级巨星职业生涯最后几年都很羞辱城市映像——北京（1）真心求建议找程序员东岸到西岸/西岸到东岸 relocation package一般是多少？想着刷题打工的还是看看这个吧Background check会check我现在在的公司吗?美国最赚钱的专业有哪些，看完很失望，文科生没出路啊圣地亚哥高通员工跳楼自杀 曾毕业于清华大学zoom ceo 袁征的中文名的拼音是什么？