根据前序、中序构造二叉树
一道有意思的题,可以很好地了解树的遍历
- 各小节会给出阶段/核心代码
- 在附录中有完整的代码
问题描述
有一棵二叉树,其前序序列为 [ 3 , 9 , 20 , 15 , 7 ] [3,9,20,15,7] [3,9,20,15,7],其中序序列为 [ 9 , 3 , 15 , 20 , 7 ] [9,3,15,20,7] [9,3,15,20,7],那么,该如何通过这两个序列构唯一造出一棵二叉树呢?
树的遍历
首先我们需要了解树的遍历是如何实现的?
假设有一棵树,其树型如下(其实就是问题描述中的树型):
3/ \
9 20/\15 7
- 前序遍历,其遍历方式可以用
DLR
来表示,代表当遍历到一个节点,优先查看其自身D
,再按照左孩子L
、右孩子R
的顺序查看
其实现代码与结果如下,大家可结合来理解:
void pre(TreeNode* u)
{if (u) {cout << u->val << " ";pre(u->left);pre(u->right);}
}
输出:
3 9 20 15 7
- 中序遍历,其遍历方式可以用
LDR
来表示,代表的内容可根据上面的解释理解
其实现代码与结果如下,大家可结合来理解:
void in(TreeNode* u)
{if (u) {in(u->left);cout << u->val << " ";in(u->right);}
}
输出:
9 3 15 20 7
- 后序序遍历,其遍历方式可以用
LRD
来表示,代表的内容可根据上面的解释理解
其实现代码与结果如下,大家可结合来理解:
void post(TreeNode* u)
{if (u){post(u->left);post(u->right);cout << u->val << " ";}
}
输出:
9 15 7 20 3
问题分析
现在,我们已经了解了树的遍历,现在回过去看一下问题,我们该如何构造二叉树?
以下的叙述大家可结合上一节,树的遍历中的例子理解
- 找到当前树的根节点
- 我们可以发现,前序遍历的第一个元素,它一定是根节点
- 找到左右两棵子树
- 我们可以发现,在中序遍历序列中,当你知道了根节点,其左边一定是该节点的左子树,右边一定是该节点的右子树
- 可以结合中序遍历的
LDR
思考
- 基于
2、3
,我们可以递归地向下执行,即从根节点开始,分割左右子树,再从左右子树继续深入,直到叶节点
代码实现
- 例题:105. 从前序与中序遍历序列构造二叉树
- 理解了下面的代码后可以去尝试解例题
AC
之后,可以思考一下,如何通过中序、后序构造二叉树- 题目链接:106. 从中序与后序遍历序列构造二叉树
/*** pl: 前序遍历的左边界; pr: 前序遍历的右边界* il: 中序遍历的左边界; ir: 中序遍历的右边界* pre: 前序遍历序列; in: 中序遍历序列
*/
TreeNode* build(int pl, int pr, int il, int ir, int* pre, int* in)
{// 获取根节点的值int root_val = pre[pl];// 找到根节点在中序遍历中的位置int k = 0;while (in[k] != root_val) k ++;// 构建根节点TreeNode* root = new TreeNode(root_val);// 当中序遍历序列中, 根节点的左边还有位置, 代表当前树有左子树/*** 参数说明* pl + 1: pl对应根节点, 则其左子树一定从pl + 1开始, 对应左子树的左边界* il, k - 1:当前根节点, 对应中序遍历中, 左子树的左右边界* 左子树的数量是固定的, 可以用k - 1 - il表示, 所以在前序遍历中pl + 1 + (k - 1 - il)对应左子树的右边界* */if (il < k) root->left = build(pl + 1, pl + 1 + (k - 1 - il), il, k - 1, pre, in);// 当中序遍历序列中, 根节点的右边还有位置, 代表当前树有右子树/*** 参数说明* pl + 1 + (k - 1 - il) + 1: 左子树右边界 + 1 -> 右子树左边界* pr: 右子树右边界* k + 1, ir: 当前根节点, 对应中序遍历中, 右子树的左右边界*/if (k < ir) root->right = build(pl + 1 + (k - 1 - il) + 1, pr, k + 1, ir, pre, in);return root;
}
附录
树的遍历与完整样例实现
#include <iostream>using namespace std;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) {}
};void pre(TreeNode* u)
{if (u) {cout << u->val << " ";pre(u->left);pre(u->right);}
}void in(TreeNode* u)
{if (u) {in(u->left);cout << u->val << " ";in(u->right);}
}void post(TreeNode* u)
{if (u){post(u->left);post(u->right);cout << u->val << " ";}
}/*** pl: 前序遍历的左边界; pr: 前序遍历的右边界* il: 中序遍历的左边界; ir: 中序遍历的右边界* pre: 前序遍历序列; in: 中序遍历序列
*/
TreeNode* build(int pl, int pr, int il, int ir, int* pre, int* in)
{// 获取根节点的值int root_val = pre[pl];// 找到根节点在中序遍历中的位置int k = 0;while (in[k] != root_val) k ++;// 构建根节点TreeNode* root = new TreeNode(root_val);// 当中序遍历序列中, 根节点的左边还有位置, 代表当前树有左子树/*** 参数说明* pl + 1: pl对应根节点, 则其左子树一定从pl + 1开始, 对应左子树的左边界* il, k - 1:当前根节点, 对应中序遍历中, 左子树的左右边界* 左子树的数量是固定的, 可以用k - 1 - il表示, 所以在前序遍历中pl + 1 + (k - 1 - il)对应左子树的右边界* */if (il < k) root->left = build(pl + 1, pl + 1 + (k - 1 - il), il, k - 1, pre, in);// 当中序遍历序列中, 根节点的右边还有位置, 代表当前树有右子树/*** 参数说明* pl + 1 + (k - 1 - il) + 1: 左子树右边界 + 1 -> 右子树左边界* pr: 右子树右边界* k + 1, ir: 当前根节点, 对应中序遍历中, 右子树的左右边界*/if (k < ir) root->right = build(pl + 1 + (k - 1 - il) + 1, pr, k + 1, ir, pre, in);return root;
}int main()
{TreeNode* root = new TreeNode(3);TreeNode* lL = new TreeNode(9);TreeNode* rL = new TreeNode(20, new TreeNode(15), new TreeNode(7));root->left = lL;root->right = rL;pre(root);puts("");in(root);puts("");post(root);puts("");int pre[5] = {3, 9, 20, 15, 7}, in[5] = {9, 3, 15, 20, 7};int n = sizeof(pre) / sizeof(int) - 1;TreeNode* construct = build(0, n, 0, n, pre, in);puts("");post(construct);return 0;
}
例题代码实现
105
class Solution {
private:TreeNode* build(int pl, int pr, int il, int ir, vector<int>& pre, vector<int>& in) {int val = pre[pl];int k = 0;while (in[k] != val) k ++;TreeNode* root = new TreeNode(val);if (il < k) root->left = build(pl + 1, pl + 1 + k - 1 - il, il, k - 1, pre, in);if (k < ir) root->right = build(pl + 1 + k - 1 - il + 1, pr, k + 1, ir, pre, in);return root;}public:TreeNode* buildTree(vector<int>& pre, vector<int>& in) {int n = pre.size() - 1;return build(0, n, 0, n, pre, in);}
};
106
class Solution {
private:TreeNode* build(int pl, int pr, int il, int ir, vector<int>& in, vector<int>& post) {int val = post[pr];int k = 0;while (in[k] != val) k ++;TreeNode *root = new TreeNode(val);if (il < k) root->left = build(pl, pl + (k - 1 - il), il, k - 1, in, post);if (k < ir) root->right = build(pl + (k - 1 - il) + 1, pr - 1, k + 1, ir, in, post);return root;}public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = inorder.size() - 1;return build(0, n, 0, n, inorder, postorder);}
};