题解 | #从中序与后序遍历序列构造二叉树#
从中序与后序遍历序列构造二叉树
https://www.nowcoder.com/practice/ab8dde7f01f3440fbbb7993d2411a46b
描述
给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。
数据范围：二叉树的节点数满足 1 \le n \le 1000 \1≤n≤1000 ，节点上的值满足 |val| \le 10^9 \∣val∣≤109 ，保证节点的值各不相同
例如输入[2,1,4,3,5],[2,4,5,3,1]时，
根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5}，如下图所示：
示例1
输入：
[1],[1]复制
返回值：
{1}
复制
示例2
输入：
[2,1,4,3,5],[2,4,5,3,1]复制
返回值：
{1,2,3,#,#,4,5}
解题思路：
根据中序遍历和后序遍历的规则确定根节点
注意做子树的长度的计算
注意左右子树起始位置的传参计算
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
TreeNode* func(vector<int>& inorder, int inBegin, int inEnd, vector<int>& postorder, int postBegin, int postEnd) {
if (inBegin < 0 || inEnd >= inorder.size() || inBegin > inEnd) {
return NULL;
}
if (postBegin < 0 || postEnd >= postorder.size() || postBegin > postEnd) {
return NULL;
}
TreeNode* head = new TreeNode(postorder[postEnd]);
int index;
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == postorder[postEnd]) {
index = i;//根节点索引
}
}
int leftsize = index - inBegin;
head->left = func(inorder, inBegin, index-1, postorder, postBegin, postBegin+leftsize-1);
head->right = func(inorder, index+1 ,inEnd, postorder, postBegin+leftsize, postEnd-1);
return head;
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
if (inorder.size() == 0 || postorder.size() == 0) {
return {};
}
TreeNode* head = func(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
return head;
}
};
投递小米集团等公司10个岗位 >
