Leetcode上105，106题很相似，都是重构二叉树的题
题目：
105:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
给定一个二叉树的前序和中序遍历的结果，要求推测构造出对应二叉树
106：
给定一个二叉树的中序和后序遍历的结果，要求推测构造出对应二叉树
解题思路
首先我们知道各个遍历的顺序，先序遍历：根 左 右
中序遍历：左 根 右
后序遍历：左 右 根
我们可以根据这些规则作出解题思路
105题
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
我们首先通过先序遍历 ，可以知道根为 3
而知道根为3后，通过中序遍历，可以知道 左子树包含 9， 右子树包含 15，20，7
这时候 我们就可以将先序遍历划分为3段 ，根3，左子树{9},右子树{20 15 17}
我们在重复刚才的步骤，可以不断向下推进，从而得到整个树的结构
对于 106题，这一次将前序改为了后序遍历，其实原理大致一样，因为后序遍历的顺序是 左 右 根
所以这一次我们要从 尾部开始搜索。
代码：
105:
/**
* 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:
int findIndex(vector<int>&inorder, int start, int end, int key){
int i;
for(i=start;i<=end;i++){
if(inorder[i] == key)
break;
}
return i;
}
TreeNode* buildStep(vector<int>& preorder, vector<int>& inorder,int start, int end ,int p_start){
if(start>end||p_start<0) return NULL;
int mid=findIndex(inorder,start,end,preorder[p_start]);
TreeNode * root= new TreeNode(preorder[p_start]);
root->left=buildStep(preorder,inorder,start,mid-1,p_start+1);
root->right=buildStep(preorder,inorder,mid+1,end,p_start+mid-start+1);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildStep(preorder,inorder,0,preorder.size()-1,0);
}
};
106
/**
* 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:
int findIndex(vector<int>&inorder, int start, int end, int key){
int i;
for(i=start;i<=end;i++){
if(inorder[i] == key)
break;
}
return i;
}
TreeNode* buildStep( vector<int>& inorder,vector<int>& postorder,int start, int end ,int p_start){
if(start>end||p_start<0) return NULL;
int mid=findIndex(inorder,start,end,postorder[p_start]);
TreeNode * root= new TreeNode(postorder[p_start]);
root->right=buildStep(inorder,postorder,mid+1,end,p_start-1);
root->left=buildStep(inorder,postorder,start,mid-1,p_start-1-end+mid);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildStep(inorder,postorder,0,postorder.size()-1,postorder.size()-1);
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
