首页 > 代码库 > 【leetcode】Construct Binary Tree from Inorder and Postorder Traversal
【leetcode】Construct Binary Tree from Inorder and Postorder Traversal
问题：
由中序和后序遍历构造二叉树。
分析：
Construct Binary Tree from Preorder and Inorder Traversal
//实现
TreeNode *addNode(vector<int> &inorder, int s1, int end1, vector<int> &postorder, int s2, int end2)
{
if(s1 > end1 || s2 > end2)
return NULL;
//construct the root
TreeNode *root = new TreeNode(postorder[end2]);
//index_of_root: the index of root in inorder.
int i = s1;
for(; i <= end1; ++i)
{
if(inorder[i] == postorder[end2])
break;
}
if(i > end1)
return NULL;
int dist = i - s1;
//construct the left branch
root->left = addNode(inorder, s1, i - 1, postorder, s2, s2 + dist - 1);
//construct the right branch
root->right = addNode(inorder, i + 1 , end1, postorder, s2 + dist, end2 - 1);
return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
int inLen = inorder.size();
int posLen = postorder.size();
if(inLen == 0 || posLen == 0 || inLen != posLen)
return NULL;
TreeNode *root = addNode(inorder, 0, inLen - 1, postorder, 0, posLen - 1);
return root;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。