Preorder and Inorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현
105. 순서 및 순서 횡단 에서 이 진 나 무 를 구축 관련 글:
106. Inorder 및 Postorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현
[사고방식]
이 문 제 는 전 서 를 옮 겨 다 니 고 중 서 를 옮 겨 다 니 며 이 진 트 리 를 구성 해 왔 다.우 리 는 앞 순 서 를 옮 겨 다 니 는 첫 번 째 노드 가 뿌리 노드 라 는 것 을 알 고 있 습 니 다. 중간 순 서 를 옮 겨 다 니 는 과정 에서 이 노드 를 찾 았 습 니 다. 중간 순 서 를 앞 부분 으로 나 누 는 왼쪽 하위 트 리 의 순서 와 후반 부분의 오른쪽 하위 트 리 의 순서 로 옮 겨 다 니 며 이렇게 반복 합 니 다.
public TreeNode buildTree(int[] preorder, int[] inorder) {
return createTree(preorder, 0, inorder, 0, preorder.length - 1);
}
private TreeNode createTree(int[] preorder, int preIndex, int[] inorder, int inBeg, int inEnd) {
if (preIndex >= preorder.length) return null;
int findIndex = 0;
for (int i = inBeg; i <= inEnd; i++)
if (preorder[preIndex] == inorder[i]) {
findIndex = i;
break;
}
TreeNode root = new TreeNode(preorder[preIndex]);
if (findIndex > inBeg)
root.left = createTree(preorder, preIndex + 1, inorder, inBeg, findIndex - 1);
if (findIndex < inEnd)
root.right = createTree(preorder, preIndex + 1 + findIndex - inBeg, inorder, findIndex + 1, inEnd);
return root;
}202 / 202
test cases passed. Runtime: 21 ms Your runtime beats 21.67% of javasubmissions.
최적화 환영 합 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
비귀속 이차수(전차, 중차, 후차, 잎 노드의 계산)#pragma once #include<iostream> #include<queue> #include<stack> using namespace std; template<class T> struct BinaryTree...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
