le mie informazioni di contatto
Posta[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Questa domanda riguarda ancora l'attraversamento sequenziale dei livelli, ma l'elaborazione è leggermente diversa.
Il mio pensiero iniziale su questa domanda era sbagliato perché inizialmente ci avevo pensato basandomi su questa immagine. Pensavo bastasse espandere l'ultimo nodo di ogni livello e il gioco è fatto. Tuttavia in realtà è sbagliato. Se segui questa idea, se non è presente il nodo 4 nella figura sopra, il nodo 5 non può essere affatto aggiunto al set di risultati. Quindi questa idea non è consigliabile.
Idea corretta:
Per evitare la situazione di cui sopra, è possibile espandere anche il lato sinistro. Quindi la gestione corretta è. Ogni livello e ogni nodo deve essere espanso, ma solo l'ultimo elemento di ogni livello deve essere aggiunto al set di risultati.
Come scrivere l'ultimo elemento da aggiungere al set di risultati?
Ogni livello utilizza la dimensione, quindi presta attenzione al conteggio durante il ciclo for e raccogli i risultati nell'ultimo.
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;
}
}
Basta trovare il valore medio per ogni livello.È ancora una questione del consiglio
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;
}
}
È anche una domanda modello, basta mantenere un valore massimo durante l'elaborazione di ciascuna riga.
L'unica cosa da ricordare è che il valore minimo di int è Integer.MIN_VALUE.
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;
}
}
Ho appena cambiato il metodo di espansione Invece di espandere i sottoalberi sinistro e destro, ho aggiunto direttamente l'elenco figlio allo stack.
C'è un metodo utilizzato che deve essere appreso.
ArrayDeque implementa Deque e Deque eredita l'interfaccia Queue e Queue eredita l'interfaccia Collection, quindi ha il metodo addAll. Per quanto riguarda i parametri di addAll, il suo tipo di parametro è di tipo Collection, il che significa che può ricevere qualsiasi oggetto che implementa l'interfaccia Collection. Ciò include ogni singola struttura di colonna a cui puoi pensare.
/*
// 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: la differenza dall'attraversamento sequenziale dei livelli è che ci sono cambiamenti durante l'elaborazione di ciascun livello. Quando si raggiunge ogni strato, il primo nodo deve essere eliminato separatamente. Naturalmente, dopo averlo estratto è necessario prima espanderlo, perché c'è ancora lo strato successivo. Quindi inizia ad attraversare i restanti nodi del livello. L'attraversamento è principalmente implementato dalla dimensione della que corrente Poiché il primo nodo di questo strato è stato eliminato, i inizia da =1 durante l'attraversamento. Ciò che è necessario fare durante l'elaborazione di ciascun nodo è modificare il puntamento. Cioè, il nodo successivo del primo nodo punta al secondo nodo estratto dallo stack in seguito, quindi Cur si sposta al successivo. E ricorda di espandere i nodi figlio sinistro e destro durante questo processo.
/*
// 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;
}
}
Si dedica alla ricerca tecnologica da più di 30 anni ed è esperto in vari linguaggi come Java, Linux, Javascript, php, css, ecc. Ha dato numerosi contributi nel campo dell'open source stazione di documentazione per gli sviluppatori per condividere alcuni problemi nello sviluppo della tecnologia per riferimento futuro
Posta[email protected]