二叉树 天梯赛 图文解释 + 相似题

我真的很讨厌二叉树，递归是我永远的痛

树的遍历

看图

推荐第二种（实际没区别，就是写得少点第二种，不麻烦 ）

int mx = 0;
void build(int l, int r, int root, int idx){
    mx = max(mx, idx);
    ans[idx] = aft[root];//由性质或图得，根结点的来源是后序
    if(l == r)
        return;
    int i = l;
    while(i < r && aft[root] != mid[i]){//找相同的点，那就是根
        ++i;
    }
    if(l <= i - 1)//不加会错
    build(l, i - 1, root - (r - i) - 1, idx * 2);//图写错了
    //      / 刚好对应
    if(i + 1 <= r)//不加会错
    build(i + 1, r, root - 1, idx * 2 + 1);
}

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> aft[i];
    }
    for (int i = 1; i <= n; ++i){
        cin >> mid[i];
    }
    re(ans);
    build(1, n, n, 1);
    cout << ans[1];
    for (int i = 2; i <= mx; ++i){
        if(ans[i])
        cout << " "<<ans[i];
    }
        return 0;
}

void build(int start, int end, int root, int index){
	if(start > end)//唯一条件区别
		return;
	int i = start;
	while(i <= end && aft[root] != mid[i])//这里不是小于等于也可以过，但是后面那道题就解释不清了
		++i;
	ans[index] = aft[root];//还有就是这里换了位置

	build(start, i - 1, root - (end - i) - 1, index * 2);
	build(i + 1, end, root - 1, index * 2 + 1);
}

bfs + 数组的方式（点我）
练习：二叉树遍历（已知前中求后）

void build(int l, int r, int root, int idx){//由相同逻辑得到此代码，应该没错
    mx = max(mx, idx);
    if(l > r)
        return;
    int i = l;
    ans[idx] = per[root];
    while(i < r && per[root] != mid[i]){
        ++i;
    }
    //build(l, i - 1, root + 1, idx * 2 + 1);
    //      / 刚好对应
    //build(i + 1, r, root + i + 1, idx * 2 + 2);//这是错的，我长个记性
    build(l, i - 1, root + 1, idx * 2 + 1);
    build(i + 1, r, root + i - l + 1, idx * 2 + 2);
}
/*
abdecf
dbeafc

层序： abcdef
*/

我真是傻逼啊，还专门建了个树，何必呢何必呢

string per, mid;
char ans[maxn];
int mx = 0;
void build(int l, int r, int root, int idx){
    mx = max(mx, idx);
    if(l > r)
        return;
    int i = l;
    ans[idx] = per[root];//由性质或图得，根结点的来源是后序
    while(i < r && per[root] != mid[i]){//找相同的点，那就是根
        ++i;
    }
    build(l, i - 1, root + 1, idx * 2 + 1);
    build(i + 1, r, root + (i - l) + 1, idx * 2 + 2);
    //           根的位置 + （距离） + 1 = 右子树的根
    cout << mid[i];
}
char tree[maxn];
int cnt;
void buildd(int root){
    if(root > cnt) return ;
    buildd(root * 2);
    buildd(root * 2 + 1);
    cout << tree[root];
}

int main(){
    while(cin >> per >> mid){
        re(tree);
        cnt = 0;
        re(ans);
        build(0, per.size() - 1, 0, 0);
        // for (int i = 0; i <= 2000; ++i){
        //     if(ans[i]){
        //         tree[++cnt] = ans[i];
        //         //cout << ans[i];
        //     }
        // }
        // buildd(1);
        cout << endl;
    }
        return 0;
}

这个前中得树还有一种方式，我没怎么看，参数不一样（l1, r1, l2, r2）;

这几个博客可以，我觉得，加深理解：
1
2
3
4没咋仔细看
看！规律

后中
build(start, i - 1, root - (end - i) - 1, index * 2);
build(i + 1, end, root - 1, index * 2 + 1);
前中
build(l, i - 1, root + 1, idx * 2 + 1);
build(i + 1, r, root + i - l + 1, idx * 2 + 2);
			 或者root + (i - l) + 1 更好理解

相似题：二叉树遍历（中层求先）
和之前的思路不一样的，往后面翻，单独开个part说，按之前思路会出错

这是二叉搜索树吗

这个讲的可以，还有视频
先看二叉搜索树模板：详细

#include
#include
using namespace std;
int tree[1005];
#define re(a) memset(a, 0, sizeof(a))
int n;
int cnt1 = 0, cnt2 = 0;
int b1[1005], b2[1005];
void build1(int l, int r){
    if(l > r)
        return;
    int i = l + 1, j = r;
    while(i <= r && tree[i] < tree[l])
        ++i;
    while(j > l && tree[j] >= tree[l])
        --j;
    if(i - j != 1)
        return;
    build1(l + 1, j);
    build1(i, r);
    b1[++cnt1] = tree[l];
}

void build2(int l, int r){
    if(l > r)
        return;
    int i = l + 1, j = r;
    while(i <= r && tree[i] >= tree[l])//从左往右找，之所以这样也是由于性质
        ++i;
    while(j > l && tree[j] < tree[l])//同理
        --j;
    if(i - j != 1)
        return;
    build2(l + 1, j);
    build2(i, r);
    b2[++cnt2] = tree[l];
}

int main(){
    cin >> n;
    re(tree);
    for (int i = 1; i <= n; ++i){
        cin >> tree[i];
    }
    build1(1, n);

	if(cnt1 == n){
		cout << "YES" << endl;
		for (int i = 1; i <= n; ++i){
			cout << b1[i];
			if(i < n)
				cout << " ";
		}
		return 0;
	}

	build2(1, n);

	if(cnt2 == n){
		cout << "YES" << endl;
		for (int i = 1; i <= n; ++i){
			cout << b2[i];
			if(i < n)
				cout << " ";
		}
	}
	else
		cout << "NO";
    return 0;
}

从上面两题，我们可以看出熟知二叉树的性质和这一步要干的是什么十分重要

玩转二叉树

服了，二叉树数组记得开大点，最后一个数据需要1e5

#include
#include
using namespace std;
int tree[1005];
#define re(a) memset(a, 0, sizeof(a))
int n;
int mid[10005], pre[10005];
int ans[10005];
int mx = 0;
void build(int l, int r, int root, int idx){
    mx = max(mx, idx);
    if(l > r)
        return;
    int i = l;
    ans[idx] = pre[root];
    while(i <= r && mid[i] != pre[root])
        ++i;
    build(l, i - 1, root + 1, idx * 2 + 1);
    build(i + 1, r, root - (l - i) + 1, idx * 2);//这里的idx和以往不同
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> mid[i];
    }
    for (int j = 1; j <= n; ++j){
        cin >> pre[j];
    }
    re(ans);
    build(1, n, 1, 1);
    cout << ans[1];
    for (int i = 2; i <= mx; ++i){
        if(ans[i])
            cout <<" "<< ans[i];
    }
        return 0;
}

相似题：二叉树的镜像（链表）

完全二叉树的层序遍历

#include
#include
using namespace std;

#define re(a) memset(a, 0, sizeof(a))

const int maxn = 1e5 + 5;
int a[maxn];
int ans[maxn];
int n;
int cnt = 0;

void build(int idx){
    if(idx > n)
        return;
    build(idx * 2);
    build(idx * 2 + 1);
    ans[idx] = a[++cnt];//也是由性质得到的
    //后序遍历最后一个是根节点
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    build(1);
    cout << ans[1];
    for(int i = 2; i <= n; ++i){
        cout << " "<<ans[i];
    }
    return 0;
}

二叉树遍历（中层求先）

这个解释最全

string mid, ceng;
char ans[maxn];
int mx = 0;
int c = 0;
int len;
void build(int l, int r, int l1, int r1){
    if(l > r)
        return;
    int j;
    bool flag = false;
    for (int i = l1; i <= r1; ++i){//已输出的结点是无法与之匹配上的
        for (j = l; j <= r; ++j){
            if(ceng[i] == mid[j]){
                cout << mid[j];
                flag = true;
                break;
            }
        }
        if(flag)
            break;
    }
    build(l, j - 1, l1, r1);
    build(j + 1, r, l1, r1);
}

int main() {
	IOS;
    cin >> mid >> ceng;
    len = mid.size();
    re(ans);
    build(0, len - 1, 0, len - 1);
        return 0;
}

所有的这些都是为了找出根节点

这个方法真的好简单，所以我之前错过了什么啊，迅速回去看别的方法

…去看并查集了，这个不一定考，考了不一定能得分，并查集起码还可以骗，看天意吧，花了两天时间了，有机会再复盘