2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Bei dieser Frage geht es immer noch um die sequentielle Durchquerung von Ebenen, die Verarbeitung unterscheidet sich jedoch geringfügig.
Meine anfänglichen Überlegungen zu dieser Frage waren falsch, da ich zunächst auf der Grundlage dieses Bildes darüber nachgedacht habe. Ich dachte, ich müsste nur den letzten Knoten jeder Ebene erweitern und das war’s. Allerdings ist es tatsächlich falsch. Wenn Sie dieser Idee folgen und es in der obigen Abbildung keinen Knoten 4 gibt, kann der Knoten 5 überhaupt nicht zur Ergebnismenge hinzugefügt werden. Daher ist diese Idee nicht ratsam.
Richtige Idee:
Um die obige Situation zu verhindern, kann auch die linke Seite erweitert werden. So ist die richtige Handhabung. Jede Ebene und jeder Knoten muss erweitert werden, aber nur das letzte Element jeder Ebene muss zum Ergebnissatz hinzugefügt werden.
Wie schreibe ich das letzte Element, das der Ergebnismenge hinzugefügt wird?
Jede Ebene verwendet die Größe. Achten Sie daher auf die Zählung während der for-Schleife und sammeln Sie die Ergebnisse in der letzten Ebene.
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;
}
}
Finden Sie einfach den Durchschnittswert für jede Ebene.Es ist immer noch eine Vorstandsfrage
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;
}
}
Es handelt sich ebenfalls um eine Vorlagenfrage. Behalten Sie bei der Verarbeitung jeder Zeile einfach einen Maximalwert bei.
Das Einzige, was Sie beachten sollten, ist, dass der Mindestwert von int Integer.MIN_VALUE ist.
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;
}
}
Ich habe gerade die Erweiterungsmethode geändert, anstatt die linken und rechten Teilbäume zu erweitern, sondern die untergeordnete Liste direkt zum Stapel hinzugefügt.
Es gibt darin eine Methode, die erlernt werden muss.
ArrayDeque implementiert Deque, Deque erbt die Queue-Schnittstelle und Queue erbt die Collection-Schnittstelle, sodass es über die addAll-Methode verfügt. In Bezug auf die Parameter von addAll ist der Parametertyp der Sammlungstyp, was bedeutet, dass jedes Objekt empfangen werden kann, das die Sammlungsschnittstelle implementiert. Dazu gehört jede einzelne Spaltenstruktur, die Sie sich vorstellen können.
/*
// 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;
}
}
Idee: Der Unterschied zur schichtsequenziellen Durchquerung besteht darin, dass es bei der Verarbeitung jeder Schicht zu Änderungen kommt. Beim Erreichen jeder Ebene muss der erste Knoten separat herausgenommen werden. Natürlich muss er nach dem Herausnehmen zuerst erweitert werden, da noch die nächste Ebene vorhanden ist. Beginnen Sie dann mit dem Durchlaufen der verbleibenden Knoten der Ebene. Die Durchquerung wird hauptsächlich durch die Größe der aktuellen Warteschlange implementiert. Da der erste Knoten dieser Schicht herausgenommen wurde, beginnt i während der Durchquerung bei =1. Während der Verarbeitung jedes Knotens muss die Ausrichtung geändert werden. Das heißt, der nächste Knoten des ersten Knotens zeigt auf den zweiten Knoten, der später aus dem Stapel entnommen wird, und wechselt dann zum nächsten Knoten. Und denken Sie daran, während dieses Vorgangs die linken und rechten untergeordneten Knoten zu erweitern.
/*
// 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;
}
}
Er widmet sich seit mehr als 30 Jahren der Technologieforschung und beherrscht verschiedene Sprachen wie Java, Linux, Javascript, PHP, CSS usw. Er hat viele Beiträge im Open-Source-Bereich geleistet, Entwicklerdokumentationsstation, um einige Themen in der Technologieentwicklung als zukünftige Referenz zu teilen
