树形dp技巧，多叉树转二叉树

今天复习树形dp时发现一道比较古老的题，叫选课，是树形dp的一道基础题，也是多叉树转二叉树应用的模版题

多叉树转二叉树的应用非常广泛，因为如果一个节点的儿子太多，一个一个存下来不方便去查询，并且会增加复杂度，但是这里我们就有一个O(n)的复杂度的方法把多叉树转换为二叉树，转换成二叉树后就更方便查询，因为每个节点最多就两个儿子节点，减少了复杂度并且让代码实现起来更容易

 

多叉树转二叉树图示：

在这张图中，右边那棵二叉树由左边的多叉树转换而来，并且这棵二叉树是竖着相连的是父子关系，横着相连的是兄弟关系，也就是左儿子，右兄弟

接着就是代码实现了，其实代码实现也有一些小小的技巧

比如我们要求输入a,b表示a是b的儿子

例子： 2 1 

           4 1

           3 1

如果我们按着顺序处理，那1的左儿子就是2,2的右儿子是4,4的右儿子是3，但是这样的话会有一点的麻烦，所以我们就不断的变更

方法：1的左儿子是2，读入第二行，4的右儿子就是当前1的左儿子节点2，然后1的左儿子变成4，读入第三行，3的右儿子是节点4，然后1的左儿子变成3

这种方法在代码上更加容易实现并且复杂度也要小一些

转换成代码就是

for(int i=1;i<=n;i++)
{

cin>>a>>b;

tree[a].right=tree[b].left;

tree[b].left=a;
}

代码就是这样，然后推荐一道模拟题，叫做选课，不过我还不知道出处，但是后面我会把这道题补到我的博客