0.前言
好久没有更新博客了，勤劳的我决定上传一些关于树的不是那么常见的代码。
在这篇博客中，首先会给出树的前序创建（递归），然后会给出“左儿子-右兄弟”第i层遍历的两种方式，包括非递归和递归，这里的递归我觉得很有意思，最后会给出一个递归地查找两个节点最近祖先的方法。
这三部分内容可以很好地展现树的递归性质带来很多精彩的递归算法。
1.普通二叉树的先序递归创建
一颗二叉搜索树可以通过不断插入节点来创建，但是一颗普通的二叉树我们应该如何创建呢？很容易想到的是使用“中-左-右”先序来创建。这里我用“#“表示空节点。
为了保持类的设计思路，对于每一个递归函数都只提供一个public的启动函数，它会调用递归函数，后面的也是这样的。
//启动函数
void PreCreate()
{
cout<<"以先序输入，输入#代表空"<<endl;
root=PreOrderCreate();
}
//递归函数
Node* PreOrderCreate()
{
string x;
cin>>x;
if(x=="#")
{
return nullptr;
}
Node*tmp=new Node(stoi(x),nullptr,nullptr);
tmp->left=PreOrderCreate();
tmp->right=PreOrderCreate();
return tmp;
}
2.“左儿子-右兄弟”树的第i层遍历
非递归很容易想到的思路是使用两个队列，一个队列叫now，它保持当前层的所有节点不断扫描，如果遇到一个有child的节点就进入，然后将那个节点所有brother进入next队列。每一次结束我们交换两个队列，即之前的next成为被扫描的now，之前now已经空了所以现在next也为空了。
void PrintLevel2(Node *root,int level)
{
if(root==nullptr)
return;
int count=1;
queue<Node *> now;
queue<Node *> next;
now.push(root);
while(count!=level)
{
while(!now.empty())
{
Node *tmp=now.front();now.pop();
if(tmp->child)
{
next.push(tmp->child);
tmp=tmp->child;
while(tmp->brother)
{
next.push(tmp->brother);
tmp=tmp->brother;
}
}
}
now.swap(next);
count++;
}
while(!now.empty())
{
Node *tmp=now.front();now.pop();
cout<<tmp->val<<' ';
}
}
递归的方法就比较精妙了。先来考虑递归边界：1.如果为空我们应该立即返回上一层。2.如果进入到了我们需要打印的那一层，那么我们唯一需要做的就是打印当前节点，并且打印它的所有兄弟——注意到这可以通过递归完成。
接下来思考如何转移状态，很容易想到不会遇到层数比我们需要的更深的情况（在那之前已经退出函数了）。那么如果遇到层数比我们低的，我们递归打印它的child并使传入的level减少1，然后原封不动把信息传给它的brother节点，完成递归。
递归算法很精炼但是思考难度较大。
void PrintLevel(Node *root,int level)
{
if(root==nullptr)
return;
if(level==1)
{
cout<<root->val<<' ';
PrintLevel(root->brother,level);
}
if(level!=1&&root->child)
{
PrintLevel(root->child,level-1);
PrintLevel(root->brother,level);
}
}
3.最早公共祖先
很经典的问题，这个递归算法很精妙很简单，每一行都在不同情况起着不同作用。
Node *closetGrandFather(Node* p,Node* q)
{
return closetGrandFather(root,p,q);
}
Node *closetGrandFather(Node*root,Node* p,Node* q)
{
if(root==nullptr||root==p||root==q)//遇到这些情况说明要不没找到（null），要不找到了
{
return root;//注意这里我们排除了一个特殊情况即p或q是最早祖先
}
Node* l=closetGrandFather(root->left,p,q);
Node* r=closetGrandFather(root->right,p,q);
if(l&&r)//左右都有信息说明分布在两边，那么root就是最早祖先了
{
return root;
}
return l==nullptr?r:l;//只有一边有信息，说明祖先节点在那一边路径上
//因为这是最外层递归了，所以节点信息其实可能在更深层，是一轮一轮传上来的
}
好啊，hin好啊