已知前序（后序）遍历序列和中序遍历序列构建⼆叉树
（Leetcode相关题⽬）
1.⽂字描述：
已知⼀颗⼆叉树的前序（后序）遍历序列和中序遍历序列，如何构建这棵⼆叉树？
以前序为例⼦：
前序遍历序列：ABCDEF
中序遍历序列：CBDAEF
先序中序后序遍历二叉树前序遍历先访问根节点，因此前序遍历序列的第⼀个字母肯定就是根节点，即A是根节点；然后，由于中序遍历先访问左⼦树，再访问根节点，最后访问右⼦树，所以我们到中序遍历中A的位置，然后A左边的字母就是左⼦树了，也就是CBD是根节点的左⼦树；同样的，得到EF为根节点的右⼦树。
将前序遍历序列分成BCD和EF，分别对左⼦树和右⼦树应⽤同样的⽅法，递归下去，⼆叉树就成功构建好了。如下图：
假如已知的是中序和后序遍历的序列，原理也⼀样。由于后序是先访问左⼦树，然后访问右⼦树，最后访问根节点，因此我们确定后序遍历序列的最后⼀个字母为根节点。其他步骤⼀样，⽤中序遍历序列出两棵⼦树，再进⾏同样的操作。
2.代码实现：
（1）已知前序和中序：
Leetcode题⽬：
105 Construct Binary Tree from Preorder and Inorder Traversal（leetcode/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/）
代码：
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return NULL;
TreeNode *res;
res = new TreeNode(preorder[preStart]);
int flag;
for (int i = inStart; i <= inEnd; i++) {
if (preorder[preStart] == inorder[i]) {
flag = i;
break;
}
}
res->left = buildTree(preorder, inorder, preStart + 1, preStart + flag - inStart, inStart, flag - 1);
res->right = buildTree(preorder, inorder, preStart + flag - inStart + 1, preEnd, flag + 1, inEnd);
return res;
}
};
⼀开始我采⽤的做法是遇到的每棵⼦树都⽤新的vector数组来存放它的中序和前序遍历序列，但这样⼜浪费空间⼜增加时间，我们只要⽤原来的vector数组就可以了。
因此我们要⽤preStart，preEnd，inStart和inEnd来保存序列开始和结束的位置。⽐较容易得出的是inStart和inEnd这两个位置；难理解的是左⼦树的preEnd和右⼦树的preStart。但是我们求出左⼦树的preEnd后，只要加1就是右⼦树的preStart了。⽽要求左⼦树的preEnd我们可以通过中序来求出左⼦树的元素个数，然后就可以求出这个位置了。
（1）已知中序和后序：
Leetcode题⽬：
106 Construct Binary Tree from Inorder and Postorder Traversal（leetcode/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/）
代码：
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTree(inorder, postorder, 0, inorder.size() - 1, postorder.size() - 1, 0);
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postEnd, int postStart) {
if (inStart > inEnd || postEnd < postStart) {
return NULL;
}
int flag;
TreeNode *res = new TreeNode(postorder[postEnd]);
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == postorder[postEnd]) {
flag = i;
break;
}
}
res->left = buildTree(inorder, postorder, inStart, flag - 1, postStart - inStart + flag - 1, postStart);
res->right = buildTree(inorder, postorder, flag + 1, inEnd, postEnd - 1, postEnd - inEnd + flag);
return res;
}
};

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。