105. Construct Binary Tree from Preorder and Inorder Traversal
程序员文章站
2022-03-03 10:21:41
...
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
class Solution {
public:
TreeNode* createTree(vector<int>& preorder,int pre_start,int pre_end,vector<int>& inorder,int in_start,int in_end)
{
if(pre_start>pre_end)
return NULL;
int root = preorder[pre_start];
int index;
for(int i=in_start;i<=in_end;i++)
{
if(inorder[i] == root)
index = i;
}
int len = index - in_start;
TreeNode* left = createTree(preorder,pre_start+1,pre_start+len,inorder,in_start,index-1);
TreeNode* right = createTree(preorder,pre_start+len+1,pre_end,inorder,index+1,in_end);
TreeNode* node = new TreeNode(root);
node->left = left;
node->right = right;
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size()==0||inorder.size()==0)
return NULL;
return createTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
};
下一篇: 关键字过滤实现
推荐阅读
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode106. Construct Binary Tree from Inorder and Postorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal