c***n
发帖数: 921 | 1 Finding deepest node of tree??
Here is a solution:
- First to find the height of the tree.(do it recursively, O(n) time)
- Then traverses through each node, find the current depth and compare
it with the maxDepth.
- If condition satisfied, print out the item stored in the node.
这是最好方法么？ |
a***9
发帖数: 364 | 2 of course not. There is no reason you can't do it one-pass.
【在 c***n 的大作中提到】
: Finding deepest node of tree??
: Here is a solution:
: - First to find the height of the tree.(do it recursively, O(n) time)
: - Then traverses through each node, find the current depth and compare
: it with the maxDepth.
: - If condition satisfied, print out the item stored in the node.
: 这是最好方法么？
|
C***y
发帖数: 2546 | 3 弄个全局变量记录当前的depth，再弄两个全局变量，一个记录已知最深的depth，另外
一个记录对应的node
这样一遍就可以了吧
【在 c***n 的大作中提到】
: Finding deepest node of tree??
: Here is a solution:
: - First to find the height of the tree.(do it recursively, O(n) time)
: - Then traverses through each node, find the current depth and compare
: it with the maxDepth.
: - If condition satisfied, print out the item stored in the node.
: 这是最好方法么？
|
g***s
发帖数: 3811 | 4 no. one scan is ok and extra O(depth(tree)) space(just for recursive
stack) is enough.
some one already gave the algo in today's post.
time)
compare
【在 c***n 的大作中提到】
: Finding deepest node of tree??
: Here is a solution:
: - First to find the height of the tree.(do it recursively, O(n) time)
: - Then traverses through each node, find the current depth and compare
: it with the maxDepth.
: - If condition satisfied, print out the item stored in the node.
: 这是最好方法么？
|
g**e
发帖数: 6127 | 5 O(n) time one pass
public static int findDiameter(BST t) {
return findDiameter(t.root, new Height(0));
}
private static int findDiameter(Node n, Height h) {
if (n==null) {
h.height = 0;
return 0;
}
Height lheight = new Height(0);
Height rheight = new Height(0);
int ldiameter = findDiameter(n.left, lheight);
int rdiameter = findDiameter(n.right, rheight);
h.height = 1 + max(lheight.height, rheight.height);
return max(lheight.height+rheight.height+1, max(ldiameter,
rdiameter));
}
private static int max(int a, int b){
return a>b?a:b;
}
private static class Height {
int height = 0;
public Height(int h){
this.height = h;
}
}
【在 g***s 的大作中提到】
: no. one scan is ok and extra O(depth(tree)) space(just for recursive
: stack) is enough.
: some one already gave the algo in today's post.
:
: time)
: compare
|
i**********e
发帖数: 1145 | 6 Why not use BFS?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
c******t
发帖数: 391 | 7 你那个方法是说以每个结点作为root来traversal？感觉这样的结果不是最深的结点，
而是这个BST的diameter诶，不知道对不对。
【在 c***n 的大作中提到】
: Finding deepest node of tree??
: Here is a solution:
: - First to find the height of the tree.(do it recursively, O(n) time)
: - Then traverses through each node, find the current depth and compare
: it with the maxDepth.
: - If condition satisfied, print out the item stored in the node.
: 这是最好方法么？
|
r******r
发帖数: 700 | 8 这个运行了一下，好像不对。 the path to the deepest node 就是树的 height. 如
果计算 height:
int height(BSTNode node) {
if (node == null)
return 0;
else
return Math.max(height(node.left), height(node.right)) + 1;
}
这就可以吧。height 的定义：
“The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.”
不过原问题好像是要找到 nodes, 那应该是 a list of nodes that have
the same biggest depth (tree's height). Something like:
ArrayList> deepestNodes(BSTNode node){
}
【在 g**e 的大作中提到】
: O(n) time one pass
: public static int findDiameter(BST t) {
: return findDiameter(t.root, new Height(0));
: }
:
: private static int findDiameter(Node n, Height h) {
: if (n==null) {
: h.height = 0;
: return 0;
: }
|
g**e
发帖数: 6127 | 9 你说的对，我没仔细看题。我的code是找BST的diameter，跟height不是一回事。
diameter可以比height大。
have
【在 r******r 的大作中提到】
: 这个运行了一下，好像不对。 the path to the deepest node 就是树的 height. 如
: 果计算 height:
: int height(BSTNode node) {
: if (node == null)
: return 0;
: else
: return Math.max(height(node.left), height(node.right)) + 1;
: }
: 这就可以吧。height 的定义：
: “The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.”
|
r******r
发帖数: 700 | 10 如果计算 deepest node 的整数值，那就是树的高度吧：
“The height of a tree is the length of the path from the root to the
deepest node in the tree. A (rooted) tree with only one node (the root) has
a height of zero.”
这个整值只有一个，就是树的高度。但这个问题的本意好像不是计算树的高度。
但如果要找出具体的 nodes，可能有多个。
看了网上一些相关话题，好像 depth 和 height 的概念有些混淆。比如有计算 最大深
度 的讨论，
public int maxDepth(BSTNode node) {
if (node == null) return 0;
int left = maxDepth(node.left);
int right = maxDepth(node.right);
return 1 + Math.max(left, right);
}
这个不就是 height 吗。
【在 g**e 的大作中提到】
: 你说的对，我没仔细看题。我的code是找BST的diameter，跟height不是一回事。
: diameter可以比height大。
:
: have
|
g**e
发帖数: 6127 | 11 我理解的BST depth=height， diameter=任意两个节点之间的最长距离
has
【在 r******r 的大作中提到】
: 如果计算 deepest node 的整数值，那就是树的高度吧：
: “The height of a tree is the length of the path from the root to the
: deepest node in the tree. A (rooted) tree with only one node (the root) has
: a height of zero.”
: 这个整值只有一个，就是树的高度。但这个问题的本意好像不是计算树的高度。
: 但如果要找出具体的 nodes，可能有多个。
: 看了网上一些相关话题，好像 depth 和 height 的概念有些混淆。比如有计算 最大深
: 度 的讨论，
: public int maxDepth(BSTNode node) {
: if (node == null) return 0;
|
r******r
发帖数: 700 | 12 root
node_k
node_n
我理解的是从 root -> node_k 的距离，是 node_k 的 depth;
从 node_k -> node_n 的距离，是 node_k 的 height
root's height = depth of node_n
root's depth = 0
node_n's height =0;
node_k's height = node_n - node_k
到 root 的最大相等路径的 leaf node 可能有多个，所以 deepest nodes 可能有多个。
from wiki:
# The depth of a node n is the length of the path from the root to the node.
The set of all nodes at a given depth is sometimes called a level of the
tree. The root node is at depth zero.
# The height of a tree is the length of the path from the root to the
deepest node in the tree. A (rooted) tree with only one node (the root) has
a height of zero. |
g**e
发帖数: 6127 | 13 我的意思是对一整棵BST来说的， 不是针对某个node。我觉得对一个BST来说，它的高
度和深度是一回事
个。
node.
has
【在 r******r 的大作中提到】
: root
: node_k
: node_n
: 我理解的是从 root -> node_k 的距离，是 node_k 的 depth;
: 从 node_k -> node_n 的距离，是 node_k 的 height
: root's height = depth of node_n
: root's depth = 0
: node_n's height =0;
: node_k's height = node_n - node_k
: 到 root 的最大相等路径的 leaf node 可能有多个，所以 deepest nodes 可能有多个。
|
d*******l
发帖数: 338 | 14 也有书上说二叉树高度和深度是差1的关系，对于单个节点好像缺乏特别权威特别统一
的定义。
不过这个题目到没有这种歧义。BFS应该就行
【在 g**e 的大作中提到】
: 我的意思是对一整棵BST来说的， 不是针对某个node。我觉得对一个BST来说，它的高
: 度和深度是一回事
:
: 个。
: node.
: has
|
