106. Inorder 및 Postorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현
Inorder 와 Postorder Traversal 에서 Binary Tree 를 구축 합 니 다.
Preorder and Inorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현
[사고방식]
이 문 제 는 중 서 를 옮 겨 다 니 고 후 서 를 옮 겨 다 니 며 이 진 트 리 를 구성 합 니 다.그 기본 적 인 사 고 는 바로 뒷 순 서 를 옮 겨 다 니 는 마지막 수의 값 을 찾 은 다음 에 중간 순 서 를 옮 겨 다 니 며 이 값 을 찾 는 것 이다.이 값 을 뿌리 로 하여 중간 순 서 를 왼쪽, 오른쪽 하위 트 리 서열 로 나 누 었 습 니 다. 앞의 순 서 는 왼쪽 하위 트 리 의 중간 순서 로 나 누 었 고 뒤의 순 서 는 오른쪽 하위 트 리 의 중간 순서 로 나 누 었 습 니 다.이 상태 에서 좌우 하위 트 리 로 돌아 가기:
public TreeNode buildTree(int[] inorder, int[] postorder) {
return createTree(inorder, 0, postorder.length - 1, postorder,
postorder.length - 1);
}
private TreeNode createTree(int[] inorder, int inBeg, int inEnd,
int[] postorder, int postIndex) {
if (postIndex < 0) return null;
int mid = 0;
for (int i = inBeg; i <= inEnd; i++)
if (inorder[i] == postorder[postIndex]) {
mid = i;
break;
}
TreeNode root = new TreeNode(inorder[mid]);
if (mid - inBeg > 0) // 0。 postIndex - (inEnd - mid) - 1 postorder
root.left = createTree(inorder, inBeg, mid - 1, postorder, postIndex - (inEnd - mid) - 1);
if (inEnd - mid > 0) // 0。 <span style="font-family: Arial, Helvetica, sans-serif;">postIndex - 1 postorder </span>
root.right = createTree(inorder, mid + 1, inEnd, postorder, postIndex - 1);
return root;
}202 / 202
test cases passed. Runtime: 21 ms Your runtime beats 17.86% of javasubmissions.
최적화 환영 합 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
