leetcode || 106、Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
Hide Tags
Tree Array Depth-first Search
제목: 두 갈래 나무의 중차 역행 서열과 후속 역행 서열을 정하고 이 두 갈래 나무를 구축하는 것도 고전적이다
thinking:
(1) 이런 유형의 문제는 예를 들어 그 규칙을 찾아내야 한다.두 갈래 나무(1,2,3,4,5,6,7)에 대한 중서 역력: 4,2,5,1,6,3,7 후속 역력: 4,5,2,6,7,3,1
먼저 뿌리 결점 1은 후속 역행 서열의 마지막 위치에서 중차 역행 서열에서find1의 위치, 1은 왼쪽 나무, 1은 오른쪽 나무입니다.하위 트리 노드 수량을 알면,
마찬가지로 후속 역행 서열도 좌우 트리를 구분할 수 있다.
(2) 상기 과정을 반복한다
code:
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if (inorder.size() == 0)
return NULL;
return make(inorder.begin(),inorder.end(),postorder.begin(),postorder.end());
}
protected:
template<class it>
TreeNode *make(it pFirst,it pLast,it qFirst,it qLast)
{
if(pFirst==pLast)
return NULL;
it loc1 = qLast-1;
int a = *loc1;
it loc2=find(pFirst,pLast,a);
int left_size=loc2-pFirst;
TreeNode *root=new TreeNode(a);
root->left=make(pFirst,loc2,qFirst,qFirst+left_size);
root->right=make(loc2+1,pLast,qFirst+left_size,qLast-1);
return root;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
