오름차순 단일 체인 테이블/수조를 균형 트리 BST로 변환
단일 체인 테이블을 지정합니다. 그 중의 요소는 오름차순으로 정렬됩니다. 이를 균형 두 갈래 검색 트리(BST)로 바꾸십시오
귀속:o(nlogn)
문제 해결 방법:
1. 체인 시계의 중점mid를 찾으면,
2.mid 접두사를 기록하고 체인 시계를 끊는다
3. 나무에mid를 넣는다
4. 헤드(왼쪽 체인 테이블),mid.next(오른쪽 체인 테이블)import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode
* @return TreeNode
*/
//
public ListNode getmid(ListNode head){
ListNode slow=head;
ListNode fast=head;
ListNode pre_slow=null;// slow
//
while(fast!=null&&fast.next!=null){
pre_slow=slow;
slow=slow.next;
fast=fast.next.next;
}
if(pre_slow!=null) pre_slow.next=null;//
return slow;
}
public TreeNode sortedListToBST (ListNode head) {
if(head==null){
return null;
}
ListNode mid=this.getmid(head);
//
TreeNode node=new TreeNode(mid.val);
// , node
if(head==mid){
return node;
}
node.left=sortedListToBST(head);
node.right=sortedListToBST(mid.next);
return node;
}
}
오름차순 정렬된 그룹을 제공하여 균형 두 갈래 검색 트리(BST)로 변환
1. 판공
2. 좌자수, 우자수import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param num int
* @return TreeNode
*/
public TreeNode getBST(int[]num,int left,int right){
if(num==null ||num.length<=0|| left>right){
return null;
}
//
int mid=left+(right-left+1)/2;
//
if(left==right){
return new TreeNode(num[left]);
}
//
TreeNode root=new TreeNode(num[mid]) ;
//
root.left=getBST(num,left,mid-1);
//
root.right=getBST(num,mid+1,right);
return root;
}
public TreeNode sortedArrayToBST (int[] num) {
if(num==null ||num.length==0){
return null;
}
return getBST(num,0,num.length-1);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode
* @return TreeNode
*/
//
public ListNode getmid(ListNode head){
ListNode slow=head;
ListNode fast=head;
ListNode pre_slow=null;// slow
//
while(fast!=null&&fast.next!=null){
pre_slow=slow;
slow=slow.next;
fast=fast.next.next;
}
if(pre_slow!=null) pre_slow.next=null;//
return slow;
}
public TreeNode sortedListToBST (ListNode head) {
if(head==null){
return null;
}
ListNode mid=this.getmid(head);
//
TreeNode node=new TreeNode(mid.val);
// , node
if(head==mid){
return node;
}
node.left=sortedListToBST(head);
node.right=sortedListToBST(mid.next);
return node;
}
}
1. 판공
2. 좌자수, 우자수
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param num int
* @return TreeNode
*/
public TreeNode getBST(int[]num,int left,int right){
if(num==null ||num.length<=0|| left>right){
return null;
}
//
int mid=left+(right-left+1)/2;
//
if(left==right){
return new TreeNode(num[left]);
}
//
TreeNode root=new TreeNode(num[mid]) ;
//
root.left=getBST(num,left,mid-1);
//
root.right=getBST(num,mid+1,right);
return root;
}
public TreeNode sortedArrayToBST (int[] num) {
if(num==null ||num.length==0){
return null;
}
return getBST(num,0,num.length-1);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.