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就是最长路径。
|
|