a********x
发帖数: 1502 | | f*********i
发帖数: 197 | 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********t
发帖数: 5706 | 3 BFS.如果node有parent 指针的话
【在 a********x 的大作中提到】
: 如何求解呢？
| c********t
发帖数: 5706 | 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********t
发帖数: 5706 | 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
| c*****a
发帖数: 808 | |
|
