【第十二届蓝桥杯】左儿子右兄弟

十二届蓝桥杯】左儿子右兄弟"/>

【第十二届蓝桥杯】左儿子右兄弟

今天我们来看一道有关树的递归题。（这几天被动归吊打55555，看道递归解解闷）

递归题大多是写法比较简洁，思路比较巧妙，这一道题也不例外。

闲话少说，我们来看一下原题：

首先，我们来介绍一下所谓“左孩子右兄弟”表示方法。（如果已经了解可以直接跳过）

对于一棵普通的树，我们可以通过一套操作将它转化为二叉树，

1.找到所有孩子数>2的父节点

2.将它的孩子节点相连

3.父节点只保留一个连向孩子节点（通常是最左边的）的边，其余所有边全部删去

4.整理一下，原来就有的边作为左指树，新加的边作为右指树

正是因为兄弟节点之间的无序，所以这个转化操作不是固定的，有很多种转化方式。

那我们如何来找这所有方式中高度最大的那一种呢？

我看到这道题目时，第一反应是递归，因为树的这种结构本来就对递归非常地友好。

在实现过程中，有一些烧脑的问题。

Q1：如何存储多叉树？

A：用邻接表，每个节点只记录它的孩子节点。

Q2：递归到什么情况为止？

A：递归到叶子结点，返回它的高度0（题目中单个节点高度默认0）。

Q3：怎么递归？

A：...

其实我们可以先直观地感受一下，如果我们把>2的兄弟节点标号排序的话，那么标号在最后一个节点它的深度是最大的，整棵任意节点的高度就等于高度加深度，所以如果我们想要获得更大的高度，只需要把高度最大的那个节点找出来，将它放到最后一个即可。

这样的话，递归关系就出来了，找到高度最大的孩子节点，加上它距离原来的父节点的深度。

时间复杂度：将所有节点扫了一遍，应该是O(n)吧。

#include<bits/stdc++.h>//手残党必备
using namespace std;
int N;int f;vector<int> v[100005];
int height(int node)
{int m=0;//初始化for(int i=0;i<v[node].size();i++)m=max(m,height(v[node][i]));//递归,找最大高度的孩子节点return m+v[node].size();//高度+深度
}
int main()
{cin>>N;for(int i=2;i<=N;i++){cin>>f;v[f].push_back(i);}cout<<height(1);//递归return 0;
}

思路有点烧脑，但代码写起来却异常的简洁，或许这就是递归的精髓吧！

感谢能看到最后，有不足的地方还望各路大佬交流指正^^