2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Cette question concerne toujours le parcours séquentiel des couches, mais le traitement est légèrement différent.
Ma réflexion initiale sur cette question était erronée car j'y ai d'abord pensé sur la base de cette image. Je pensais qu'il me suffisait d'étendre le dernier nœud de chaque couche et c'est tout. Cependant, c’est en fait faux. Si vous suivez cette idée, s'il n'y a pas de nœud 4 dans la figure ci-dessus, alors le nœud 5 ne peut pas du tout être ajouté à l'ensemble de résultats. Cette idée n’est donc pas recommandée.
Bonne idée :
Afin d'éviter la situation ci-dessus, le côté gauche peut également être agrandi. La manipulation correcte est donc. Chaque couche et chaque nœud doivent être développés, mais seul le dernier élément de chaque couche doit être ajouté au jeu de résultats.
Comment écrire le dernier élément à ajouter au jeu de résultats ?
Chaque couche utilise la taille, alors faites attention au comptage pendant la boucle for et collectez les résultats lors de la dernière.
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;
}
}
Trouvez simplement la valeur moyenne pour chaque couche.C'est toujours une question du conseil d'administration
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;
}
}
C'est aussi une question modèle, il suffit de conserver une valeur maximale lors du traitement de chaque ligne.
La seule chose à retenir est que la valeur minimale de int est 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;
}
}
Je viens de changer la méthode d'expansion. Au lieu d'étendre les sous-arbres gauche et droit, j'ai directement ajouté la liste des enfants à la pile.
Il y a une méthode utilisée qui doit être apprise.
ArrayDeque implémente Deque, et Deque hérite de l'interface Queue, et Queue hérite de l'interface Collection, il a donc la méthode addAll. Concernant les paramètres de addAll, son type de paramètre est de type Collection, ce qui signifie qu'il peut recevoir n'importe quel objet qui implémente l'interface Collection. Cela inclut toutes les structures de colonnes auxquelles vous pouvez penser.
/*
// 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;
}
}
Idée : La différence avec le parcours séquentiel de couches est qu'il y a des changements lors du traitement de chaque couche. Lorsque vous atteignez chaque couche, le premier nœud doit être supprimé séparément. Bien sûr, il doit d'abord être développé après l'avoir supprimé, car il reste encore la couche suivante. Commencez ensuite à parcourir les nœuds restants de la couche. Le parcours est principalement implémenté par la taille du que actuel Puisque le premier nœud de cette couche a été supprimé, je commence à =1 pendant le parcours. Ce qu'il faut faire lors du traitement de chaque nœud, c'est modifier le pointage. Autrement dit, le nœud suivant du premier nœud pointe vers le deuxième nœud retiré de la pile plus tard, puis cur passe au suivant. Et n'oubliez pas de développer les nœuds enfants gauche et droit pendant ce processus.
/*
// 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;
}
}
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
