Leetcode - Verify Preorder Sequence in Binary Search Tree
사고방식1: 폭력법은 현재 검사를 기다리는 수조를 두루 훑어보고 첫 번째 수조의 시작 위치보다 큰 위치 i를 찾으면 i는 오른쪽 나무 뿌리 노드이고 귀속적으로 좌우 나무를 판단한다.루트 노드에 대해 최악의 경우 전체 수조를 두루 돌아다녀야 한다. 시간은 O(N)이다. 각 노드를 차례로 검사해야 하기 때문에 전체 시간 복잡도는 O(N^2)이다.
사고방식2: Stefan Pochmann 대신의 작품 참고https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space, 시간 복잡도는 O(N), 공간 복잡도는 O(h)입니다.
public class Solution {
// Method 2
public boolean verifyPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) return true;
LinkedList<Integer> stack = new LinkedList<Integer>();
int low = Integer.MIN_VALUE;
for (int i = 0; i < preorder.length; i++) {
if (preorder[i] < low) return false;
while (!stack.isEmpty() && preorder[i] > stack.peek()) {
low = stack.pop();
}
stack.push(preorder[i]);
}
return true;
}
// Method 1: brute force
public boolean verifyPreorder1(int[] preorder) {
if (preorder == null) return false;
return recur(preorder, 0, preorder.length - 1);
}
public boolean recur(int[] preorder, int start, int end) {
if (start >= end) return true;
int i = start + 1;
while (i <= end && preorder[i] < preorder[start])
i++;
if (!recur(preorder, start + 1, i - 1))
return false;
int rightStart = i;
while (i <= end && preorder[i] > preorder[start])
i++;
if (i <= end) return false;
return recur(preorder, rightStart, end);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
