моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Этот вопрос по-прежнему касается последовательного обхода слоев, но обработка немного отличается.
Мои первоначальные мысли по этому вопросу были неправильными, потому что изначально я думал об этом, основываясь на этой картинке. Я подумал, что мне просто нужно расширить последний узел каждого слоя и всё. Однако на самом деле это неправильно. Если следовать этой идее, то если на рисунке выше нет узла 4, то узел 5 вообще нельзя будет добавить в набор результатов. Так что эта идея нецелесообразна.
Правильная идея:
Чтобы предотвратить описанную выше ситуацию, левую сторону также можно расширить. Итак, правильное обращение. Каждый слой и каждый узел необходимо расширить, но в набор результатов необходимо добавить только последний элемент каждого слоя.
Как написать последний элемент, который будет добавлен в набор результатов?
Каждый слой использует размер, поэтому обратите внимание на подсчет во время цикла for и собирайте результаты в последнем.
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;
}
}
Просто найдите среднее значение для каждого слоя.Это все еще вопрос совета директоров
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;
}
}
Это также шаблонный вопрос: просто сохраняйте максимальное значение при обработке каждой строки.
Единственное, что нужно помнить, это то, что минимальное значение 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;
}
}
Я просто изменил метод расширения. Вместо расширения левого и правого поддеревьев я напрямую добавил дочерний список в стек.
В нем используется метод, который необходимо изучить.
ArrayDeque реализует Deque, а Deque наследует интерфейс Queue, а Queue наследует интерфейс Collection, поэтому у него есть метод addAll. Что касается параметров addAll, то его тип параметра — тип коллекции, что означает, что он может получить любой объект, реализующий интерфейс коллекции. Это включает в себя каждую структуру столбцов, о которой вы только можете подумать.
/*
// 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;
}
}
Идея: Отличие от последовательного обхода слоев заключается в том, что при обработке каждого слоя происходят изменения. Дойдя до каждого слоя, первый узел нужно вынимать отдельно. Разумеется, его нужно сначала развернуть после вынимания, ведь есть еще следующий слой. Затем начните обход остальных узлов слоя. Обход в основном реализуется размером текущей очереди. Поскольку первый узел этого слоя был удален, во время обхода я начинаю с =1. Что необходимо сделать во время обработки каждого узла, так это изменить наведение. То есть следующий узел первого узла указывает на второй узел, извлеченный из стека позже, а затем cur переходит к следующему. И не забудьте во время этого процесса расширить левый и правый дочерние узлы.
/*
// 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;
}
}
Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.
Почтамезофия@protonmail.com