[leetcode 문제 풀이 시리즈] Construct Binary Tree from Preorder and Inorder Traversal
동시에 총괄적으로 말하자면, 만약에 앞의 반복과 뒤의 반복만 제시한다면, 우리는 이 두 갈래 나무를 확정할 수 없다. 왜냐하면 언제든지 앞의 반복과 뒤의 반복은 상반되기 때문이다.
우리는 이 두 갈래 나무의 구조를 판단할 길이 없다.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
TreeNode * dfs(int in_left, int in_right, vector<int> & inorder,
int pre_left, int pre_right, vector<int> & preorder){
if(in_left > in_right)
return 0;
TreeNode * ret = new TreeNode(preorder[pre_left]);
for(int i = in_left; i <= in_right; ++ i)
if(inorder[i] == preorder[pre_left]){
ret->left = dfs(in_left, i - 1, inorder, pre_left + 1, pre_left + 1+ i - 1 - in_left, preorder);
ret->right = dfs(i + 1, in_right, inorder, pre_right - (in_right - i - 1), pre_right, preorder);
return ret;
}
return 0;
}
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(inorder.size() <= 0)
return 0;
return dfs(0, inorder.size() - 1, inorder, 0, preorder.size() - 1, preorder);
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
