검지offer-이차수 재건
1397 단어 검지offer
문제 풀이 사고방식: 두 갈래 나무의 앞 순서에서 첫 번째 숫자는 항상 나무의 루트 노드이지만 중간 순서에서 루트 노드의 값은 서열의 중간에 있고 왼쪽 트리의 서열은 루트 노드의 왼쪽에 있고 오른쪽 트리의 서열은 루트 노드의 오른쪽에 있다.따라서 앞의 순서와 중간의 왼쪽 트리와 오른쪽 트리의 순서를 확인하기 위해 중간 순서에서 루트 노드의 위치를 찾아야 한다.트리 구축은 귀속 구조를 사용할 수 있습니다.tips: 중간 시퀀스에서 트리의 루트 노드의 위치를 정하고 HashMap을 사용하면 과정의 복잡도를 O(1)로 만들 수 있습니다.
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//
Map map = new HashMap<>();
for(int i=0;i map) {
// TODO Auto-generated method stub
// ，
//
if(start_pre>end_pre){
return null;
}
TreeNode root = new TreeNode(pre[start_pre]);
// ， HashMap
int rootIndex = map.get(pre[start_pre]);
int leftLen = rootIndex - start_in;
int pre_left = start_pre + leftLen;
root.left = createTree(pre, start_pre+1, pre_left, in, start_in, rootIndex-1, map);
root.right = createTree(pre, pre_left+1, end_pre, in, rootIndex+1, end_in, map);
return root;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
