Pointer 传递陷阱
今天试了一道leetcode简单题，发现出现了一个很奇怪的错误，leetcode是按照层序的顺序来构建二叉树的，如果当前层都没有元素了，就不print，也就结束了，如果父亲没有 jing号(markdown语法都不知道怎么print jing号，他是强调的含义o(╯□╰)o)
也不print，总是有点怪怪的，可能和CreatBT这个函数有关，举个例子
1
/ \
2 3
/
4
\
5
构建BT的序列是 “{1,2,3,#,#,4,#,#,5}”， 如果二叉树显示的不好。详见https://oj.leetcode.com/problems/symmetric-tree/
思路就是层序遍历，因为要区分层，所以采用了编程之美的经典算法(我没有看清题目说明，题目说了初始的next都是NULL，其实不需要区分层的，普通队列层序遍历就可以了，没有赋next的刚好都是应该赋NULL = = 就当又温习了一遍这个算法)，
vector模拟一个队列，利用current和last区分层，具体详见编程之美。题目说的constant空间 感觉好瞎啊，这个必须遍历BT，要么递归，要么用栈(先中后序)，要么队列(层序)，logn的空间我感觉都少不了的。。。。队列极端装了一层的点，
最大是最多结点的一层，2^(h-1)=n/2, h=下限(logn)+1 或者 上限(log(n+1)), 栈则是h，O(logn),递归也是栈一样，O(logn)
void connect(TreeLinkNode *root)
{
if(root==NULL) return;
vector<TreeLinkNode* > vec;
vec.push_back(root);
int current=0;
TreeLinkNode* lastp;
while(current<vec.size())
{
int last=vec.size();//the final one's next one
int i=0;
while(current<last)
{
TreeLinkNode* p=vec.at(current);
if(i>0)
lastp->next=p;//level first one, do not have last
lastp=p;
cout<<p->val;
if(p->left)
vec.push_back(p->left);
if(p->right)
vec.push_back(p->right);
current++;
i++;
}
lastp->next=NULL;//level last next is null
cout<<endl;
}
}
后来发现第一个case死活过不了，而且感觉很奇怪，
Input: {0}
Output: 0
Expected: {0,#}
{0，#}是啥样的二叉树啊，如果是0 输出就是0啊，如果是有个左(右)孩子1，就是{0,1,#}({0,#,1})。。。不知道这个啥意思。。。导致现在都没过。。。
悲剧了，昨天收到邮件，一个回复说你的cout要删掉= = o(╯□╰)o 我才知道这个低级的错误，往往我们会忽视最简单的错误，而且写的这个可以处理各种二叉树，于是后面一道也过了。。。。
另外看到一个递归算法，中科大的一个童鞋写的，他也利用了初始值为NULL这个性质，将BT分为left right 两个BT，然后递归，两个子BT处理完了，还有一部分next没处理，也即两个BT 每一层，left最后一个指向right第一个，用一个用个
while一直探下去直到没有了为止
void connect(TreeLinkNode *root) {
if( root == NULL || root->left == NULL || root->right == NULL ) //{0} 有一个为空就不处理，其实不会出现left right一个空一个不空的，因为题目说了完全BT，而且即使有了，算法也会出问题。。。。
{
return;
}
TreeLinkNode *p, *q;
p = root->left;
q = root->right;
p->next = q;
while( p->right != NULL && q->left != NULL )//处理两个子BT之间的那些指针
{
p = p->right;
q = q->left;
p->next = q;
}
connect( root->left );
connect( root->right );
}
看起来是elegant, 但是不能处理非完全二叉树，很有局限性，例如1左->2右->3， 2只有左子树4，无右子树，那么这个4是需要指向右孩子3子树的下一层第一个结点，这个指针指不到这个地方，这大概也是为啥这个题目分了两类吧。。。。
https://wangxj.blog.ustc.edu.cn/?p=31
于是乎打算自己构建一颗二叉树来测，回想起当年CM老师教的(先序遍历)递归构建二叉树的算法(中序和后序递归建立BT可能会有问题，不太确定)，当时记得融神还不太熟悉这个算法，自己一个一个的手动insert左孩子或者右孩子。。。
于是乎我写一遍，一遍没好，调递归算法是最蛋疼的，你无法想象蛋会有多疼，一层一层的局部变量进去，我是先序或者某个序输出来看的，递归一定要记得有出口。后来终于发现了一个忽视的问题，指针传递其实也是值传递，也即传递这个指针变量的
值(地址值，指向一个变量存储的地址)，然后里面都是new出来的结点，于是穿进去之后，会是OS分配的一个新的某个地址，于是传入的参数就指不到这个地址了，于是树挂了。。。。我发现CM老师的课件也有这个问题好像当时还没人纠正。。。
这里应当也必须改为指针的引用传递，这样才可以保证传入的是指针变量，让这个指针变量申请一个新的堆空间，地址存在这个指针变量里。
修改后的先序遍历构建二叉树代码(-1 表示此处空)
void Create(TreeLinkNode* & root)
{
int data;
cin>>data;
if(data == -1) root=NULL;
else
{
root=new TreeLinkNode(data);
Create(root->left);
Create(root->right);
}
}
这个递归其实也是有递归出口的，看起来大家都习惯了一上来必须是递归出口。如果输入-1，就不递归了，递归出口的定义就是这个分支不会继续递归下去，而是在有限步后就停止了，这也是某歌07年的笔试题里一个选择提到过的。
另外自己Copy代码的时候，经常会出问题，虽然fawks大神当时也建议我copy一些，提高效率，但是我总会忘记把改改的改完，例如先序Copy到中序，只有定义的函数名改了，里面递归调用没改，于是出现了一种全新的遍历顺序 #_#