二叉树的遍历

四种遍历方式，除层序遍历，其余三种在于根的输出位置不同

先序遍历

遍历顺序：根 -> 左子树 -> 右子树

代码模板，以0表示空

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int tree[N];
int n;

void dfs(int root)
{
    if (!tree[root]) return ; // 递归到空节点返回

    cout << tree[root] << ' '; // 输出根节点
    dfs(root << 1); // 递归左子树
    dfs(root << 1 | 1); // 递归右子树
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> tree[i];

    dfs(1);

    return 0;
}

中序遍历

遍历顺序：左子树 -> 根 -> 右子树

代码模板

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int tree[N];
int n;

void dfs(int root)
{
    if (!tree[root]) return ;

    dfs(root << 1);
    cout << tree[root] << ' ';
    dfs(root << 1 | 1);
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> tree[i];

    dfs(1);

    return 0;
}

后序遍历

遍历顺序：左子树 -> 右子树 -> 根

代码模板

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int tree[N];
int n;

void dfs(int root)
{
    if (!tree[root]) return ;

    dfs(root << 1);
    dfs(root << 1 | 1);
    cout << tree[root] << ' ';
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> tree[i];

    dfs(1);

    return 0;
}

当给定中序遍历和其他一种遍历方式就可以创建一棵树，

但题目往往会让我们得出其他的遍历形式

根据先序遍历、中序遍历得出后序遍历

模板题： AcWing 3598. 二叉树遍历

代码：

#include <iostream>
#include <vector>

using namespace std;

const int M = 1e5 + 10;

char in[M], pre[M];
int n;
vector<char> post;

void dfs(int root, int start, int end)
{
    if (start > end) return ;

    int i = start;
    while (i <= end && in[i] != pre[root]) i ++;

    dfs(root + 1, start, i - 1);
    dfs(root + 1 + (i - start), i + 1, end);

    post.push_back(pre[root]);
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> pre[i];
    for (int i = 1; i <= n; i ++) cin >> in[i];

    dfs(1, 1, n);

    for (int i = 0; i < post.size(); i ++)
        cout << post[i];

    return 0;
}

根据后序遍历、中序遍历得出先序遍历

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n;
char post[N], in[N];
vector<char> pre;

void dfs(int root, int l, int r)
{
    if (l > r) return ;

    int i = l;
    while (i < r && in[i] != post[root]) i ++;

    pre.push_back(post[root]);
    dfs(root - 1 - (r - i), l, i - 1);
    dfs(root - 1, i + 1, r);
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++) cin >> post[i];
    for (int i = 0; i < n; i ++) cin >> in[i];

    dfs(n - 1, 0, n - 1);

    for (int i = 0; i < pre.size(); i ++)
        cout << pre[i];

    return 0;
}

根据后序遍历、中序遍历得出层序遍历

模板题： AcWing 1497. 树的遍历

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int M = 100 + 10;

int post[M], in[M];
map<int, int> ans;
int n;

void find(int root, int st, int ed, int idx)
{
    if (st > ed) return ;
    ans[idx] = post[root];
    int i = st;
    while (i <= ed && in[i] != post[root]) i ++;
    find(root - 1 - (ed - i), st, i - 1, idx << 1);
    find(root - 1, i + 1, ed, idx << 1 | 1);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> post[i];
    for (int i = 1; i <= n; i ++) cin >> in[i];

    find(n, 1, n, 1);

    bool flag = 0;
    for (auto i : ans)
    {
        if (flag) cout << ' ';
        cout << i.second;
        flag = 1;
    }

    return 0;
}