二叉树专题

Complete Binary Search Tree (30)

Link
这道题相当于是已知完全二叉排序树的中序遍历，要输出其层序遍历。做法很巧妙，根本不用建树。

1. #include <iostream>
2. #include <cstdio>
3. #include <cstdlib>
4. #include <algorithm>
5. #include <string>
6. #include <string.h>
7. #include <vector>
8. #include <cmath>
9. #include <unordered_set>
10. using namespace std;
11. int n,cur;
12. int a[1010],b[1010];
13. void levelTraverse(int r){
14.         if(r<=n){
15.                 levelTraverse(r<<1);
16.                 b[r]=a[++cur];
17.                 levelTraverse((r<<1)+1);
18.         }
19. }
20. int main() {
21.         scanf("%d",&n);
22.         for(int i=1;i<=n;++i)
23.                 scanf("%d",&a[i]);
24.         sort(a+1,a+1+n);
25.         levelTraverse(1);
26.         for(int i=1;i<n;++i)
27.                 printf("%d ",b[i]);
28.         printf("%d\n",b[n]);
29.         return 0;
30. }

复制代码

Is It a Binary Search Tree (25)

Link
根据BST的前序遍历输出其后序遍历。不用建树。
[code]#include #include #include #include #include #include #include using namespace std;int n;int a[1010];bool isMirror=false;bool isBST=true;vectorans;void build(int l,int r){        if(!isBST||l>r) return;        int root=a[l];        if(isMirror){                int i=l+1;                for(;i