构建二叉树
本文图文并茂讲解从前序遍历、中序续遍历构建二叉树或者从后序遍历、中序续遍历又或者从前序遍历、后序续遍历构建二叉树的原理,比附上相关的习题。
1. 从前序遍历、中序续遍历构建二叉树
题目一
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. 从后序遍历、中序续遍历构建二叉树
题目一
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;
}
};
题目二
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;
}