首页 > 试题广场 >

一棵树节点 1,2,3,.....,n 怎样实现，先进行 O

[问答题]

一棵树节点 1,2,3, .....,n 怎样实现，先进行  O(n)  预处理。然后任给两个节点，用 O(1) 判断它们的父子关系

添加回答
Nickqiao头像 Nickqiao
dfs一遍，记录每个结点的开始访问时间Si和结束访问时间Ei  对于两个节点i,j，若区间[Si,Ei]包含[Sj,Ej]，则i是j的祖先

发表于 2017-03-01 20:05:17 回复(0)
提交观点

问题信息

复杂度 树
上传者：牛100
难度：
1条回答 1745浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号