두 갈래 나무 - 중차적 역류와 후차적 역류 나무 구조 두 갈래 나무 - 중등
2030 단어 LintCode
묘사
중차 역류와 후차 역류 트리에 따라 두 갈래 트리를 구성한다
너는 트리에 같은 수치의 노드가 존재하지 않는다고 가정할 수 있다
당신은 실제 면접에서 이 문제를 만난 적이 있습니까?예.
예제
나무의 중서 역행을 제시한다:[1,2,3]과 후서 역행:[1,3,2]
다음 트리로 돌아갑니다.
2
/ \
1 3
제목 링크
프로그램
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param inorder: A list of integers that inorder traversal of a tree
* @param postorder: A list of integers that postorder traversal of a tree
* @return: Root of a tree
*/
TreeNode * buildTree(vector &inorder, vector &postorder) {
// write your code here
TreeNode * root = NULL;
vector l_postorder, r_postorder, l_inorder, r_inorder;
int i, root_index = 0;
if(postorder.empty() != 1 || inorder.empty() != 1){
//
root = new TreeNode(postorder[postorder.size() - 1]);
//
for(i = 0; i < inorder.size(); i++){
if(postorder[postorder.size() - 1] == inorder[i])
break;
root_index++;
}
// 、
for(i = 0; i < root_index; i++){
l_inorder.push_back(inorder[i]);
l_postorder.push_back(postorder[i]);
}
for(i = root_index + 1; i < inorder.size(); i++){
r_inorder.push_back(inorder[i]);
r_postorder.push_back(postorder[i-1]);
}
root->left = buildTree(l_inorder, l_postorder);
root->right = buildTree(r_inorder, r_postorder);
}
return root;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
lintcode--94. 두 갈래 나무의 최대 경로와두 갈래 트리를 제시하고 경로와 최대를 찾을 수 있습니다. 경로는 어느 노드에서 시작하고 끝낼 수 있습니다. (경로와 두 노드 사이에 있는 경로의 노드 값의 합) 두 갈래 나무 한 그루를 주시오. 되돌아오다 뒷순서에...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.