h*3
2 楼
以前面试中碰到过的。拿出来讨论,看看是否完整。
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)
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)
i*e
3 楼
想买些带回国自己用,不知道这个牌子那些东西比较好?
l*8
5 楼
我觉得没问题。
y*n
7 楼
首先,我们需要明确所谓的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;
: }
如果“逆行”也算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
9 楼
随便选个点,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;
: }
,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;
: }
s*y
14 楼
re
a*3
15 楼
我对这个问题的理解有点不明白。首先,这个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。
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
17 楼
我怎么觉得不对呢,人家问的是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就是最长路径。
我觉得最长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就是最长路径。
w*i
24 楼
热
p*6
25 楼
re baozi
s*r
26 楼
re
t*t
28 楼
re
g*9
30 楼
re
c*n
31 楼
re,pai
c*t
33 楼
re
y*0
34 楼
热
O*e
35 楼
re
m*s
37 楼
RE
T*u
38 楼
re
c*0
39 楼
re
w*0
41 楼
re
R*V
44 楼
RE
z*n
45 楼
re
b*n
46 楼
RE
d*l
52 楼
re
b*e
53 楼
re
a*d
58 楼
re
N*7
59 楼
re
m*o
60 楼
re
g*a
64 楼
re
c*a
65 楼
re
z*i
67 楼
re
d*g
68 楼
re
c*r
70 楼
re
b*r
72 楼
re
a*n
74 楼
re
h*5
75 楼
re
d*n
76 楼
re baozi
s*e
77 楼
re
l*8
78 楼
re
k*8
79 楼
re
d*r
80 楼
re
o*o
85 楼
re
Y*o
88 楼
re
H*C
92 楼
re
d*0
93 楼
re
D*s
95 楼
re
l*s
97 楼
re
W*t
98 楼
re
l*8
99 楼
re
P*r
100 楼
re
c*a
102 楼
Re
m*l
103 楼
re 包子
t*f
105 楼
re
a*l
106 楼
re
z*0
107 楼
re
b*o
108 楼
re
a*e
110 楼
re
s*x
111 楼
re
b*t
112 楼
rere
L*1
116 楼
re
i*8
119 楼
re
c*t
121 楼
re
n*5
122 楼
re
s*u
123 楼
re
m*a
124 楼
RE
e*i
125 楼
re
r*g
126 楼
re
t*r
127 楼
re
s*8
129 楼
re
s*0
130 楼
re
L*i
132 楼
热
i*t
135 楼
pai baozi
g*u
137 楼
RE
c*l
139 楼
re
P*r
140 楼
re
z*0
141 楼
re
s*j
143 楼
re
j*1
145 楼
re
t*1
146 楼
re
l*i
147 楼
rere
j*u
148 楼
re
y*0
149 楼
re
w*a
151 楼
re
y*8
152 楼
re
B*N
153 楼
re
m*a
155 楼
re
w*t
156 楼
re
E*e
158 楼
re
j*t
159 楼
re
相关阅读
是否应该有双黑色的帆布鞋?禁用化妆品名单场(转)求推荐香波/护发素推荐个eye make up remover吧?有没有MM来说说Sergio Rossi的鞋怎么样,ruelala上有deal我也奔个五金花婚纱照`````之前奔过了..我是不是皮肤过敏了?用过otto玫瑰精油的请进,怎么用效果好?奔一件Dress - 图在6&8楼这件婚纱是哪个牌子的?参加活动小声问一句 EL 啥时候有活动不?Target 送免费的beauty bag怎么买便宜的fissler往国内寄包裹地址写中文还是英文哒?Gwyneth Paltrow现在好青春啊!问个位牛人,知不知道一个意大利牌子的包包,大约叫Publicated之类的。。请JMs推荐款面膜,眼膜,去角质膏,说说使用心得。姐妹们在sasa.com买的东西都要多久到啊?LA MER