[LeetCode-21]Construct Binary Tree from Preorder and Inorder Traversal
Note: You may assume that duplicates do not exist in the tree.
There is an example.
_______7______
/ \
__10__ ___2
/ \ /
4 3 _8
\ /
1 11
The preorder and inorder traversals for the binary tree above is:
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
The first node in preorder alwasy the root of the tree. We can break the tree like:
1st round:
preorder: {7}, {10,4,3,1}, {2,8,11}
inorder: {4,10,3,1}, {7}, {11, 8,2}
_______7______
/ \
{4,10,3,1} {11,8,2}
Since we alreay find that {7} will be the root, and in "inorder"sert, all the data in the left of {7} will construct the left sub-tree. And the right part will construct a right sub-tree. We can the left and right part agin based on the preorder.
2nd round
left part right part
preorder: {10}, {4}, {3,1} {2}, {8,11}
inorder: {4}, {10}, {3,1} {11,8}, {2}
_______7______
/ \
__10__ ___2
/ \ /
4 {3,1} {11,8}
see that, {10} will be the root of left-sub-tree and {2} will be the root of right-sub-tree.
Same way to split {3,1} and {11,8}, yo will get the complete tree now.
_______7______
/ \
__10__ ___2
/ \ /
4 3 _8
\ /
1 11
So, simulate this process from bottom to top with recursion as following code.
c++
TreeNode *BuildTreePI(
vector<int> &preorder,
vector<int> &inorder,
int p_s, int p_e,
int i_s, int i_e){
if(p_s > p_e) return NULL;
int pivot = preorder[p_s];
int i = i_s;
for(;i<i_e;i++){
if(inorder[i] == pivot)
break;
}
int length1 = i-i_s-1;
int length2 = i_e-i-1;
TreeNode* node = new TreeNode(pivot);
node->left = BuildTreePI(preorder,inorder,p_s+1,length1+p_s+1,i_s, i-1);
node->right = BuildTreePI(preorder, inorder, p_e-length2, p_e, i+1, i_e);
return node;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
return BuildTreePI(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
}
java
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildPI(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
}
public TreeNode buildPI(int[] preorder, int[] inorder, int p_s, int p_e, int i_s, int i_e){
if(p_s>p_e)
return null;
int pivot = preorder[p_s];
int i = i_s;
for(;i<i_e;i++){
if(inorder[i]==pivot)
break;
}
TreeNode node = new TreeNode(pivot);
int lenLeft = i-i_s;
node.left = buildPI(preorder, inorder, p_s+1, p_s+lenLeft, i_s, i-1);
node.right = buildPI(preorder, inorder, p_s+lenLeft+1, p_e, i+1, i_e);
return node;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.