f*i
2 楼
Iterative inorder, when meet a leaf node, such node together with the nodes
in the stack form a path.
Time O(n)
space O(lgn)
in the stack form a path.
Time O(n)
space O(lgn)
c*t
3 楼
BFS.如果node有parent 指针的话
【在 a********x 的大作中提到】
: 如何求解呢？
【在 a********x 的大作中提到】
: 如何求解呢？
c*t
4 楼
how about using post-order? for each node, discard shorter children path,
save the longer one.
time: O(n)
space: O(length of longest path)
nodes
【在 f*********i 的大作中提到】
: Iterative inorder, when meet a leaf node, such node together with the nodes
: in the stack form a path.
: Time O(n)
: space O(lgn)
save the longer one.
time: O(n)
space: O(length of longest path)
nodes
【在 f*********i 的大作中提到】
: Iterative inorder, when meet a leaf node, such node together with the nodes
: in the stack form a path.
: Time O(n)
: space O(lgn)
c*t
5 楼
似乎可行，写了个recursion。等牛人写个iteration吧
public LinkedList longestPath(Node root) {
if (root == null)
return new LinkedList();
LinkedList leftPath = longestPath(root.left);
LinkedList rightPath = longestPath(root.right);
if (leftPath.size() >= rightPath.size()) {
leftPath.push(root);
return leftPath;
} else {
rightPath.push(root);
return rightPath;
}
}
【在 c********t 的大作中提到】
: how about using post-order? for each node, discard shorter children path,
: save the longer one.
: time: O(n)
: space: O(length of longest path)
:
: nodes
public LinkedList
if (root == null)
return new LinkedList
LinkedList
LinkedList
if (leftPath.size() >= rightPath.size()) {
leftPath.push(root);
return leftPath;
} else {
rightPath.push(root);
return rightPath;
}
}
【在 c********t 的大作中提到】
: how about using post-order? for each node, discard shorter children path,
: save the longer one.
: time: O(n)
: space: O(length of longest path)
:
: nodes
c*a
6 楼
150里面有一题很相近的啊
相关阅读
本版正确的打开方式各位努力向前跑，把所以的不公不快挫折悔恨都抛在身后，人脉和吹牛比刷题重要facebook onsite以后多久会有通知结果unidentified_titleH1b被裁 grace period只剩30天，希望好心人帮帮忙各位看官去发点内推，捞点new grad吧cs行业将来被挤成坑了怎么办？cs业内人士有何后备打算？我感觉我的运气又来了google 每年的RSU refresh 是分48个月vest吗？微软老中恶心死了Houston 石油相关公司招.net/SQL developer 需要有绿卡Amazon AWS vs Alexa【求助】是否应该归还工资？linkedin上面找国内校友内推靠谱不？刷板转芯片的请找我在哪查美国公司真实工资数据最靠谱？国内每年毕业 50 万计算机专业的研究生和本科生又到周末了 你准备怎么过?现在还有f2随便读个cs 就能找到不错的工作的吗？