Johnson_sky

分类

每日一题(1) 题目解析(10)

/ 注册

全部文章（共4篇）

[题解] Tree III

“第二直径”显然其一端的端点在直径的一端。可以尝试用反证法来进行证明，这里给出一个简单的证明，具体细节留给读者自证：若第二直径的两端都不在直径的端点，那么将第二直径的某一端向直径端点延申，得到的路径长度不降。因此，我们只需要任意找到一条直径，分别找到他们到每个点的距离，然后寻找到“第三大”的位置（...

Dfs 树

2020-05-28

1 545

[题解] Tree VI

考察点：完全二叉树的含义及其推广，Dfs序列遍历顺序需要理解完全二叉树的含义：即每个结点的子结点之多有两个子结点。不妨我们先考虑最简单的一种情况，即结点编号按照一棵“标准”完全二叉树给出，即结点的两个子结点分别为与，根据这棵树，我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。由此，我们可...

树 Dfs

2020-05-28

0 483

[题解] Tree II

考察点：完全二叉树的含义及其推广，Bfs序列遍历顺序需要理解完全二叉树的含义：即每个结点的子结点之多有两个子结点。不妨我们先考虑最简单的一种情况，即结点编号按照一棵“标准”完全二叉树给出，即结点的两个子结点分别为与，根据这棵树，我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。由此，我们可...

树 Bfs

2020-05-28

0 525

[题解] Tree IV

60~70% 可以直接对整棵树进行Dfs，即从根结点1号点开始，若当前结点为，则递归搜索两个子结点、，然后暴力计算答案，时间复杂度为，根据语言选择的不同可能会有不同的得分。 100% 本题利用了两个性质，同时这也是完全二叉树最常用的两个性质：若父结点为，则其两个子结点分别为、每一层均有个结点 ...

树完全二叉树

2020-05-27

0 561