공간 대가 대체 시간 대가 - LeetCode105 - 전차와 중차 역행 서열 구조 두 갈래 나무
。
:
。
,
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
:
3
/ \
9 20
/ \
15 7
생각
첫 번째 요소는 트리의 루트 노드입니다.중서는 이 뿌리 노드에 의해 두 부분으로 나뉘는데 왼쪽 부분은 뿌리 노드 왼쪽에 있고 오른쪽 부분은 뿌리 노드 오른쪽에 있다.각각 왼쪽 부분과 오른쪽 부분에서 뿌리 결점을 찾습니다.이렇게 차례로 돌아가다.귀속 매개 변수: 루트 노드, 루트 결점에 의해 분리된 그룹.귀속 방법: 뿌리 노드에 따라 수조를 분리하고 분리 부분의 뿌리 노드를 각각 찾아서 귀속한다.
코드
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public static Map map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0){
return null;
}
// map , , for
map = new HashMap();
for(int i=0;i
주의하다
처음 쓴 코드는 주석이 떨어진 코드로 시간을 초과합니다.시간 초과 문제를 해결하기 위해 맵 형식을 도입하여 for 순환에서 얻은 값을 맵에 저장하고 공간 대가로 시간 대가를 줄인다.
생각 2
외부 순환은 선서수 그룹을 두루 훑어보고 첫 번째 요소는 루트 노드입니다.두 번째 원소와 첫 번째 원소가 중서수 그룹의 위치를 비교하고 위치가 뿌리 결점의 왼쪽인지 오른쪽인지 판단한다.세 번째 원소와 첫 번째 원소가 중서수 그룹의 위치를 비교한다. 만약에 왼쪽에 있으면 첫 번째 원소의 왼쪽이 비어 있는지 판단하고 만약에 비어 있으면 세 번째 원소를 여기에 놓고 만약 비어 있지 않으면 세 번째 원소는 다시 첫 번째 원소의 왼쪽에 있는 원소와 두 번째 라운드를 비교한다.이렇게 유추하다.
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0){
return null;
}
TreeNode[] treenodes=new TreeNode[preorder.length];
for(int i=0;i
주의하다
시간을 초과하면 맵 형식을 이용하여 for순환을 줄이고 공간 대가로 시간 대가를 줄일 수 있습니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.