树遍历

前中后序遍历

中序和前序或后序其一可确定唯一的一棵树

• 前序和后序由于根在最先或最后，所以可以用来找根。
• 找根时，既可以使用map存储位置（不能从0开始，因为map找不到时是返回0的），也可以用while遍历比较。
• 中序根在中间，可以根据根在中序中的位置来区分左右子树，进而递归（一般使用dfs或者bfs）。

例子：
前序中序转后序
1138

void postOrder(int prel, int inl, int inr) {
	if (inl > inr || flag == true) return;
	int i = inl;
	while (in[i] != pre[prel]) i++;
		postOrder(prel+1, inl, i-1);
		postOrder(prel+i-inl+1, i+1, inr);
	if (flag == false) {
	printf("%d", in[i]);
	flag = true;
	}
}

前序和后序建树有不确定性

• 前序和后序把左右子树和根分割开来了，如果结点只有一棵子树则左右子树皆可，不唯一了。

例子：
前序后序转中序
1119

void getIn(int preLeft, int preRight, int postLeft, int postRight) {
   if(preLeft == preRight) {
   	in.push_back(pre[preLeft]);
   	return;
   }
   if (pre[preLeft] == post[postRight]) { //可以省略
   int i = preLeft + 1;
   while (i <= preRight && pre[i] != post[postRight-1]) i++; //找到右子树
   	if (i - preLeft > 1) //如果有左子树，则目前的树是唯一的
   		getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) -1);
   	else //如果没有左子树，则子树可以是左子树也可以是右子树，不唯一
   		unique = false;
   	in.push_back(post[postRight]);
   	getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
   }
}

层序遍历

• 层序，即从上到下，从左到右，按照序号遍历。
• 前中后序，皆规定先左后右，所以满足层中顺序，只需要再加上层间顺序，用自定义sort函数即可排成层序。

二叉搜索树BST

• BST中序遍历就是将所有结点排序后的结果，即二叉搜索树自带中序遍历。
• 要注意题目中对BST的定义，一般的BST是不包含重复元素的，但是题目中很可能会有重复元素（子结点>=或者<=父结点）。
• 除了使用自带中序，还可以：如果给了前序，从根节点从前往后找，找到最后一个小于根的结点即是根左子树的最后结点，根结点的下一个结点即是左子树的根结点；从结尾从后往前找，找到最后一个大于根的结点即为根右子树的根节点，结尾即是根右子树的最后结点。例子如下：

1043

void getpost(int root, int tail) {
	if(root > tail) return ;
	int i = root + 1, j = tail;
	if(!isMirror) {
		while(i <= tail && pre[root] > pre[i]) i++;
		while(j > root && pre[root] <= pre[j]) j--;
	} else {
		while(i <= tail && pre[root] <= pre[i]) i++;
		while(j > root && pre[root] > pre[j]) j--;
	}
	if(i - j != 1) return ;
	getpost(root + 1, j);
	getpost(i, tail);
	post.push_back(pre[root]);
}