左孩子右兄弟（蓝桥杯）

左孩子右兄弟（蓝桥杯）

• 问题网址 https://www.lanqiao.cn/problems/1451/learning/?contest_id=73

• 首先要明白什么是左孩子右兄弟的表示法（可将多叉树转为二叉树），如下图所示：

• 

• 其次这题目说了兄弟结点的连接顺序可以任意，孩子结点也可以任选。

• 要想让最终的深度最高，那么就要让每一层拥有最多的孩子结点的结点放到最后一个兄弟结点，但是事实上并不是最多的孩子结点都在同一个子树上。假设1为根结点，2、3、4都是它的孩子结点，而2有3个孩子结点、3没有、4也有3个，那其实孩子结点这一层的贡献最多就是加3个高度。因为分割时总有一个结点是分在前面的，那么它提供的3个高度在某种程度上是被抵消了的。

• 所以要从第二层开始，选择这第二层所有子树每层具有孩子节点总和最多的结点放到兄弟结点的最后。最多的孩子结点提供的高度最多，放到最后那么它的起始高度就比较高，抵消的高度就比较少（这里的抵消的意思是分割后有多个子树的高度都小于最高的这棵）

• 既然分割，那肯定要把具有最多孩子的兄弟结点连接到最后，起始高度大最终得到的整个树的高度就会更大。

• 具体看代码吧（可以用树形DP做也可，这里是找最大高度情况）

• #include<bits/stdc++.h>//手残党必备
  using namespace std;
  int N;int f;vector<int> v[100005];
  
  // 做这题主要就是整清楚什么情况下高度才是最大的，就是从2到n层 看每棵子树，每层都看父结点具有的最大孩子数，然后把每层的相加起来得到这棵子树可以提供的最大高度、
  // 得到全部子树可提供的最大高度取最大的，再加上第二层的结点数，因为第二层也能分产生高度。
  
  //这个就是计算以第二层各个结点为根结点的子树每层最大孩子结点数相加和的最大值。
  // 这边的node为父结点 V[node]里面存储的是以node结点为父结点的结点号码
  // 最后一次回到第一次递归时，肯定要加上根结点的结点数。因为根结点的孩子分割也能提供高度。
  int height(int node)
  {
  	int m=0;//初始化
  	for(int i=0;i<v[node].size();i++)
      // 递归,得到每个结点的孩子数，选取出最大值。
      // 记住：同一层结点是在同一个循环里面的, 就可以找到同一层这几个结点能产生最高高度的结点。
      // m就表示这一层这几个结点能产生的最大高度。
  		m=max(m,height(v[node][i]));
      // cout << "m的值为: " << m << "v[node].size()中node为: " << node << "值为: " << v[node].size() <<  endl;
      return m+v[node].size();//本身node结点的孩子数+和他孩子数下面的每层孩子数的最大值。
  }
  
  int main()
  {
  	cin>>N;
  	for(int i=2;i<=N;i++)
  	{   // f为根结点
  		cin>>f;
          // 根结点下存储着它的孩子结点的号码
  		v[f].push_back(i);
  	}
      // 从根结点开始递归
  	cout<<height(1);
  	return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35