2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Tämä kysymys koskee edelleen kerrosten peräkkäistä läpikulkua, mutta käsittely on hieman erilainen.
Alkuperäinen ajatukseni tästä kysymyksestä oli väärä, koska ajattelin sitä alun perin tämän kuvan perusteella. Ajattelin, että minun täytyy vain laajentaa jokaisen kerroksen viimeistä solmua, ja siinä se. Se on kuitenkin itse asiassa väärin. Jos noudatat tätä ideaa, jos yllä olevassa kuvassa ei ole solmua 4, solmua 5 ei voi lisätä tulosjoukkoon ollenkaan. Tämä ajatus ei siis ole suositeltavaa.
Oikea idea:
Yllä olevan tilanteen estämiseksi vasenta puolta voidaan myös laajentaa. Oikea käsittely on siis. Jokainen kerros ja jokainen solmu on laajennettava, mutta vain kunkin kerroksen viimeinen elementti on lisättävä tulosjoukkoon.
Kuinka kirjoittaa viimeinen tulosjoukkoon lisättävä elementti?
Jokainen kerros käyttää kokoa, joten kiinnitä huomiota laskemiseen for-silmukan aikana ja kerää tulokset viimeisellä.
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> que = new ArrayDeque<>();
if(root==null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
for(int i = 0;i<size;i++){
TreeNode temp = que.pollFirst();
if(i==size-1){
result.add(temp.val);
}
if(temp.left!=null){
que.offerLast(temp.left);
}
if(temp.right!=null){
que.offerLast(temp.right);
}
}
}
return result;
}
}
Etsi vain kunkin kerroksen keskiarvo.Se on edelleen hallituksen kysymys
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
Deque<TreeNode> que = new ArrayDeque<>();
if(root==null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
double sum = 0;
double avg = 0;
for(int i = 0;i<size;i++){
TreeNode temp = que.pollFirst();
sum += temp.val;
if(temp.left!=null){
que.offerLast(temp.left);
}
if(temp.right!=null){
que.offerLast(temp.right);
}
}
avg = sum/size;
result.add(avg);
}
return result;
}
}
Se on myös mallikysymys, vain säilytä enimmäisarvo jokaisen rivin käsittelyssä.
Muista vain, että int:n vähimmäisarvo on Kokonaisluku.MIN_ARVO.
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> que = new ArrayDeque<>();
if(root==null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
int max = Integer.MIN_VALUE;
for(int i = 0;i<size;i++){
TreeNode temp = que.pollFirst();
if(temp.val > max){
max = temp.val;
}
if(temp.left!=null){
que.offerLast(temp.left);
}
if(temp.right!=null){
que.offerLast(temp.right);
}
}
result.add(max);
}
return result;
}
}
Vaihdoin juuri laajennusmenetelmää Vasemman ja oikean alipuun laajentamisen sijaan lisäsin suoraan aliluettelon pinoon.
Siinä käytetään menetelmää, joka on opittava.
ArrayDeque toteuttaa Dequen, ja Deque perii Queue-rajapinnan ja Queue perii Collection-rajapinnan, joten sillä on addAll-menetelmä. Mitä tulee addAll-parametreihin, sen parametrityyppi on Collection type, mikä tarkoittaa, että se voi vastaanottaa minkä tahansa Collection-rajapinnan toteuttavan objektin. Tämä sisältää jokaisen yksittäisen sarakerakenteen, jonka voit ajatella.
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
Deque<Node> que = new ArrayDeque<>();
if(root == null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
List<Integer> curList = new ArrayList<>();
while(size>0){
Node temp = que.pollFirst();
curList.add(temp.val);
//就是扩展方式变了，变为直接把子节点全部加入到队列中，这也等价于将里面的每个元素从尾部依次加入队列当中。
que.addAll(temp.children);
size--;
}
result.add(curList);
}
return result;
}
}
Idea: Ero kerrosten peräkkäiseen läpikulkuun on se, että jokaista kerrosta käsiteltäessä tapahtuu muutoksia. Kun jokaiseen kerrokseen päästään, ensimmäinen solmu on poistettava erikseen. Tietysti sitä on ensin laajennettava poisoton jälkeen, sillä seuraava kerros on vielä jäljellä. Aloita sitten kerroksen jäljellä olevien solmujen läpikulku. Läpikulku toteutetaan pääasiassa nykyisen que:n koon mukaan. Koska tämän kerroksen ensimmäinen solmu on poistettu, i alkaa =1:stä läpikulun aikana. Jokaisen solmun käsittelyn aikana on tehtävä osoituksen muokkaaminen. Toisin sanoen ensimmäisen solmun seuraava solmu osoittaa pinosta myöhemmin poistuneeseen toiseen solmuun, ja sitten cur siirtyy seuraavaan. Ja muista laajentaa vasenta ja oikeaa lapsisolmua tämän prosessin aikana.
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Deque<Node> que = new ArrayDeque<>();
if(root==null){
return root;
}
que.offerLast(root);
while(!que.isEmpty()){
//每层先取出第一个节点
int size = que.size();
Node cur = que.pollFirst();
//扩展它
if(cur.left!=null){
que.offerLast(cur.left);
}
if(cur.right!=null){
que.offerLast(cur.right);
}
for(int i = 1;i<size;i++){
Node next = que.pollFirst();
if(next.left!=null){
que.offerLast(next.left);
}
if(next.right!=null){
que.offerLast(next.right);
}
cur.next = next;
cur = next;
}
}
return root;
}
}
Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin tässä Kehittäjän dokumentaatioasema jakaaksesi teknologian kehittämisen ongelman tulevaa käyttöä varten
