minhas informações de contato
Correspondência[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Esta questão ainda é sobre a travessia sequencial de camadas, mas o processamento é um pouco diferente.
Meu pensamento inicial sobre esta questão estava errado porque inicialmente pensei nisso com base nesta imagem. Achei que só precisava expandir o último nó de cada camada e pronto. No entanto, está realmente errado. Se você seguir esta ideia, se não houver nenhum nó 4 na figura acima, então o nó 5 não poderá ser adicionado ao conjunto de resultados. Portanto esta ideia não é aconselhável.
Idéia correta:
Para evitar a situação acima, o lado esquerdo também pode ser expandido. Então o manuseio correto é. Cada camada e cada nó precisam ser expandidos, mas apenas o último elemento de cada camada precisa ser adicionado ao conjunto de resultados.
Como escrever o último elemento a ser adicionado ao conjunto de resultados?
Cada camada usa tamanho, então preste atenção à contagem durante o loop for e colete os resultados no ú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;
}
}
Basta encontrar o valor médio de cada camada.Ainda é uma questão do conselho
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;
}
}
Também é uma questão modelo, basta manter um valor máximo ao processar cada linha.
A única coisa a lembrar é que o valor mínimo de 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;
}
}
Acabei de alterar o método de expansão. Em vez de expandir as subárvores esquerda e direita, adicionei diretamente a lista filha à pilha.
Existe um método usado nele que precisa ser aprendido.
ArrayDeque implementa Deque, e Deque herda a interface Queue e Queue herda a interface Collection, portanto possui o método addAll. Em relação aos parâmetros do addAll, seu tipo de parâmetro é do tipo Collection, o que significa que pode receber qualquer objeto que implemente a interface Collection. Isso inclui todas as estruturas de coluna que você possa imaginar.
/*
// 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;
}
}
Ideia: A diferença da travessia sequencial de camadas é que há alterações ao processar cada camada. Ao atingir cada camada, o primeiro nó precisa ser retirado separadamente. Claro, ele deve ser expandido primeiro depois de retirado, pois ainda existe a próxima camada. Em seguida, comece a percorrer os nós restantes da camada. A travessia é implementada principalmente pelo tamanho da fila atual. Como o primeiro nó desta camada foi retirado, i começa em =1 durante a travessia. O que precisa ser feito durante o processamento de cada nó é modificar o apontamento. Ou seja, o próximo nó do primeiro nó aponta para o segundo nó retirado da pilha posteriormente e, em seguida, cur passa para o próximo. E lembre-se de expandir os nós filhos esquerdo e direito durante este 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;
}
}
Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.
Correspondência[email protected]