h******3
发帖数: 351 | 1 以前面试中碰到过的。拿出来讨论，看看是否完整。
Given a binary tree, find the length of the longest path.
其实就是找树的直径：左子树高，右子树高，穿过树根的最长的path,这三个Value的最
大值
/* root of the tree, height*/
int dia(struct node *root,int* h){
if (root == null){
*h = 0;
return 0;
}
/* left tree height, right tree height*/
int lh = 0, rh = 0;
/* left subtree diameter, right subtree dia*/
int ld = 0, rd = 0;
ld = dia(root->left,&lh);
rd = dia(root->right,&rh);
*h = max(lh,rh) + 1;
return max(lh+rh+1,max(rd,ld))
}
time is O(n) | l*********8
发帖数: 4642 | | y****n
发帖数: 743 | 3 首先，我们需要明确所谓的path是否包含“逆行”的path。
如果“逆行”也算path的话，这段代码貌似有个bug。
如果输入是一个root，左右各一个叶节点，共三个节点。
这样的path长度是2，而这段代码应该会返回1。
【在 h******3 的大作中提到】
: 以前面试中碰到过的。拿出来讨论，看看是否完整。
: Given a binary tree, find the length of the longest path.
: 其实就是找树的直径：左子树高，右子树高，穿过树根的最长的path,这三个Value的最
: 大值
: /* root of the tree, height*/
: int dia(struct node *root,int* h){
: if (root == null){
: *h = 0;
: return 0;
: }
| S******t
发帖数: 151 | 4 随便选个点，DFS到最远的叶子结点A，从这个叶子结点A再DFS到离该叶子结点最远的B
，AB就是最长路径。
【在 h******3 的大作中提到】
: 以前面试中碰到过的。拿出来讨论，看看是否完整。
: Given a binary tree, find the length of the longest path.
: 其实就是找树的直径：左子树高，右子树高，穿过树根的最长的path,这三个Value的最
: 大值
: /* root of the tree, height*/
: int dia(struct node *root,int* h){
: if (root == null){
: *h = 0;
: return 0;
: }
| y****n
发帖数: 743 | 5 不好意思，好像是我对length理解错了。 :)
【在 y****n 的大作中提到】
: 首先，我们需要明确所谓的path是否包含“逆行”的path。
: 如果“逆行”也算path的话，这段代码貌似有个bug。
: 如果输入是一个root，左右各一个叶节点，共三个节点。
: 这样的path长度是2，而这段代码应该会返回1。
| h******3
发帖数: 351 | 6 三个节点 (root, left, right), length of longest path is 3. This code returns
3.
【在 y****n 的大作中提到】
: 首先，我们需要明确所谓的path是否包含“逆行”的path。
: 如果“逆行”也算path的话，这段代码貌似有个bug。
: 如果输入是一个root，左右各一个叶节点，共三个节点。
: 这样的path长度是2，而这段代码应该会返回1。
| a**********3
发帖数: 64 | 7 我对这个问题的理解有点不明白。首先，这个binary tree是不是一定要是一个rooted
tree,建立在rooted tree的基础之上谈的？也就是说，有一个vertex,也就是root,满足
id(v)=0. 如果这样的话，path就只能向着一个direction走，逆行是指什么呢？两个
vertices有两个双向的edge么？那样的话，不就create了一个cycle,不满足tree的定义
呀？tree是没有cycle的。
如果不是两个vertices之间有两个edge,而是一个的话，只能指向一个方向，怎么逆行
呢？逆行存在了以后，那谁又是root呢？
我觉得binary tree的最长path就是它的height吧？也就是从root到最远leaf的edge的
数？那这道题就是求binary tree height的问题了？
【在 y****n 的大作中提到】
: 首先，我们需要明确所谓的path是否包含“逆行”的path。
: 如果“逆行”也算path的话，这段代码貌似有个bug。
: 如果输入是一个root，左右各一个叶节点，共三个节点。
: 这样的path长度是2，而这段代码应该会返回1。
| a**********3
发帖数: 64 | 8 我怎么觉得不对呢，人家问的是path, 你这个得出的结果是walk.
我觉得最长path就是bt的height
int BinaryTree::height() {
return heightRec(root);
}
int BinaryTree::heightRec(Node *n) {
if (n==0) {
return -1;
} else {
int height_l = heightRec(n->left);
int height_r = heightRec(n->right);
int height_s = height_l;
if (height_r > height_l) {
height_s = height_r;
}
return 1+height_s;
}
}
BinaryTree::BinaryTree() {
root = 0;
}
B
★ 发自iPhone App: ChineseWeb 7.8
【在 S******t 的大作中提到】
: 随便选个点，DFS到最远的叶子结点A，从这个叶子结点A再DFS到离该叶子结点最远的B
: ，AB就是最长路径。
|
|
