构建二叉树

发布时间 2023-11-18 23:29:03作者: 爱情丶眨眼而去

构建二叉树

本文图文并茂讲解从前序遍历、中序续遍历构建二叉树或者从后序遍历、中序续遍历又或者从前序遍历、后序续遍历构建二叉树的原理,比附上相关的习题。

1. 从前序遍历、中序续遍历构建二叉树

题目一

LeetCode 105. 从前序与中序遍历序列构造二叉树

AC代码,展开查看
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i ++ ) pos[inorder[i]] = i;
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
        if(pl > pr) return nullptr;
        auto root = new TreeNode(preorder[pl]);
        int k = pos[root -> val];
        root -> left = build(preorder, inorder, pl + 1, k - il + pl, il, k - 1);
        root -> right = build(preorder, inorder, k - il + pl + 1, pr, k + 1, ir);
        return root;
    }
};

2. 从后序遍历、中序续遍历构建二叉树

题目一

LeetCode 106. 从中序与后序遍历序列构造二叉树

AC代码,展开查看
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i = 0; i < inorder.size(); i ++ ) pos[inorder[i]] = i;
        return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr){
        if(il > ir) return nullptr;
        auto root = new TreeNode(postorder[pr]);
        int k = pos[root -> val];
        root -> left = build(inorder, postorder, il, k - 1, pl, pl + k - il - 1);
        root -> right = build(inorder, postorder, k + 1, ir, pl + k - il, pr - 1);
        return root;
    }
};

题目二

洛谷 P1030 [NOIP2001 普及组] 求先序排列

AC代码,展开查看
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 10;

char mid[N], after[N];

void dfs(char m[], char a[], int ml, int mr, int al, int ar){
    if(mr >= ml){
        char c = a[ar];
        printf("%c", c);
        int t = -1;
        for(int i = ml; i <= mr; i ++ ){
            if(m[i] == c){
                t = i;
                break;
            }
        }
        if(t != -1){
            dfs(m, a, ml, t - 1, al, ar - mr + t - 1);
            dfs(m, a, t + 1, mr, t, ar - 1);
        }
    }
}

int main(){
    scanf("%s%s", mid, after);
    int n = strlen(mid);
    dfs(mid, after, 0, n - 1, 0, n - 1);
    return 0;
}

3. 从前序遍历、后序续遍历构建二叉树

题目一

LeetCode 889. 根据前序和后序遍历构造二叉树