binary tree的最长root leaf path - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

binary tree的最长root leaf path

binary tree的最长root leaf path# JobHunting - 待字闺中

a*x2012-11-08 08:11

1 楼

如何求解呢？

f*i2012-11-08 08:11

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)

c*t2012-11-08 08:11

3 楼

BFS.如果node有parent 指针的话

【在 a********x 的大作中提到】

: 如何求解呢？

c*t2012-11-08 08:11

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)

c*t2012-11-08 08:11

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