根据前序、中序构造二叉树

一道有意思的题，可以很好地了解树的遍历

• 各小节会给出阶段/核心代码
• 在附录中有完整的代码

问题描述

有一棵二叉树，其前序序列为$[3,9,20,15,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

问题分析

现在，我们已经了解了树的遍历，现在回过去看一下问题，我们该如何构造二叉树？

以下的叙述大家可结合上一节，树的遍历中的例子理解

1. 找到当前树的根节点
   • 我们可以发现，前序遍历的第一个元素，它一定是根节点
2. 找到左右两棵子树
   • 我们可以发现，在中序遍历序列中，当你知道了根节点，其左边一定是该节点的左子树，右边一定是该节点的右子树
   • 可以结合中序遍历的LDR思考
3. 基于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);}
};