Mi informacion de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Esta pregunta todavía se refiere al recorrido secuencial de capas, pero el procesamiento es ligeramente diferente.
Mi pensamiento inicial sobre esta pregunta fue incorrecto porque inicialmente lo pensé basándome en esta imagen. Pensé que solo necesitaba expandir el último nodo de cada capa y listo. Sin embargo, en realidad está mal. Si sigue esta idea, si no hay ningún nodo 4 en la figura anterior, entonces el nodo 5 no se puede agregar al conjunto de resultados en absoluto. Entonces esta idea no es aconsejable.
Idea correcta:
Para evitar la situación anterior, también se puede ampliar el lado izquierdo. Entonces el manejo correcto es. Es necesario expandir cada capa y cada nodo, pero solo es necesario agregar el último elemento de cada capa al conjunto de resultados.
¿Cómo escribir el último elemento que se agregará al conjunto de resultados?
Cada capa usa tamaño, así que preste atención a contar durante el ciclo for y recopile los resultados en el último.
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;
}
}
Simplemente encuentre el valor promedio para cada capa.Sigue siendo una pregunta de la junta
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;
}
}
También es una pregunta de plantilla, simplemente mantenga un valor máximo al procesar cada fila.
Lo único que hay que recordar es que el valor mínimo de int es 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;
}
}
Acabo de cambiar el método de expansión. En lugar de expandir los subárboles izquierdo y derecho, agregué directamente la lista secundaria a la pila.
Se utiliza un método que debe aprenderse.
ArrayDeque implementa Deque, Deque hereda la interfaz Queue y Queue hereda la interfaz Collection, por lo que tiene el método addAll. En cuanto a los parámetros de addAll, su tipo de parámetro es tipo Colección, lo que significa que puede recibir cualquier objeto que implemente la interfaz Colección. Esto incluye todas las estructuras de columnas que se te ocurran.
/*
// 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 diferencia con el recorrido secuencial de capas es que hay cambios al procesar cada capa. Al llegar a cada capa, el primer nodo debe sacarse por separado. Por supuesto, primero debe expandirse después de sacarlo, porque todavía queda la siguiente capa. Luego comience a atravesar los nodos restantes de la capa. El recorrido se implementa principalmente por el tamaño de la cola actual. Dado que se elimina el primer nodo de esta capa, i comienza desde = 1 durante el recorrido. Lo que hay que hacer durante el procesamiento de cada nodo es modificar el apuntamiento. Es decir, el siguiente nodo del primer nodo apunta al segundo nodo que salió de la pila más tarde, y luego cur pasa al siguiente. Y recuerde expandir los nodos secundarios izquierdo y derecho durante este proceso.
/*
// 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;
}
}
Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.
Correo[email protected]