Расскажите о различных позах бинарного дерева (рекурсия, AVL, BST, DFS, BFS)

алгоритм

предисловие

Предисловие: Это для того, чтобы разобраться с недавно написанными вопросами в качестве разработчика интерфейса, который учится. Эта статья представляет собой мое простое понимание алгоритма двоичного дерева и мое понимание некоторых общих идей алгоритма. Надеюсь, вы сможете прочитать статью. После что у меня есть определенное понимание общих операций с бинарными деревьями.В статье перечислены некоторые темы, которые я считаю более классическими. Любые ошибки приветствуются, чтобы указать. 😮😮😮

Эта статья была впервые опубликована в моем блоге:Алиса Коко.GitHub.IO/2020/03/06/…

Основные понятия деревьев

Определение дерева: это своего рода важная нелинейная структура данных, и это иерархическая структура, определяемая отношениями ветвления. Каждый узел имеет ноль или более дочерних узлов; узел без родительского узла называется корневым узлом; каждый некорневой узел имеет один и только один родительский узел; за исключением корневого узла каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев

Объяснение некоторых общих терминов:

  • Степень узла: количество поддеревьев, содержащихся в узле, называется степенью узла.
  • Листовой узел: узел без дочерних элементов
  • Уровень узла: начиная с корня, корень — это первый уровень, потомки корня — это второй уровень и т. д.
  • Глубина дерева: максимальное количество уровней узлов в дереве называется глубиной или высотой дерева.

бинарное дерево

Особенности бинарного дерева

Бинарное дерево состоит в том, что каждый узел имеет не более двух дочерних элементов, а левое и правое поддеревья расположены по порядку и не могут произвольно меняться местами.

полное бинарное дерево: в бинарном дереве. Если все узлы ветвления имеют левое и правое поддеревья, и все листья находятся на одном уровне, то такое бинарное дерево называется полным бинарным деревом.

满二叉树

полное бинарное дерево: Полное бинарное дерево получается из полного бинарного дерева.Если глубина бинарного дерева установлена ​​равной h, за исключением h-го слоя, количество узлов в других слоях (1~h-1) достигает максимального числа (т. е. 1~h-1. Уровень 1 — полное бинарное дерево), все узлы h-го слоя постоянно концентрируются на самом левом, что является полным бинарным деревом

完全二叉树
Решение проблемы бинарного дерева неотделима от рекурсии. Рекурсивный алгоритм Framework является прототипом многих общих алгоритмов.

О рекурсии

что такое рекурсия

Рекурсия: бесконечно вызывать функцию самой себя.Каждый вызов всегда изменяет ключевую переменную.Когда ключевая переменная достигает границы, она больше не вызывается.

Проще говоря: функция продолжает вызывать саму функцию, которая называется рекурсией.

Последнее фото, которое я отправил в круг друзей

递归复习

Рекурсивная рекурсия, сначала пройти, затем вернуться

Точно так же большая проблема (обзор) делится на множество подзадач, которые нужно решить, и подзадачи не будут разделены на подподзадачи..., (рука) наконец самая маленькая и самая маленькая подзадача решена, эта наименьшая подзадача решена Наименьшая проблема решена, получено возвращаемое значение, возвращаемое значение решает подзадачу предыдущего слоя, возвращаемое значение предыдущего слоя решает проблему предыдущего слоя ... и так далее, пока не будет решена первая проблема (возврат).

Итак, что нас должно беспокоить, так это то, какую проблему решает каждый уровень рекурсии? 🤔 Какое должно быть возвращаемое значение после решения задачи? 🤔 и текущее условие выхода для всей рекурсии.

рекурсивная ошибка

Я только начал писать рекурсивные задачи, и я не могу избавиться от линейного, пока (истинный) метод решения задач, чтобы думать, думать о том, что делает этот слой функций, и что делает следующий слой функций после она вызывает себя... Таким образом, легко запутаться (ಥ_ಥ)), вы написали рекурсию и разбили функцию на if else итерацию шаг за шагом, разве это не контрпродуктивно, (/□＼*). На самом деле нам не нужно обращать внимание на то, сколько раз должна пройти вся рекурсия и какие результаты получаются каждый раз. На самом деле, поскольку рекурсия делает одно и то же для каждого слоя, вам не нужно замыкаться в этом рекурсивном круге.Нам нужно только сосредоточиться на процессе решения одноуровневой рекурсии..

Когда использовать рекурсию?

В общем, проблемы, которые можно решить рекурсивно, имеют следующие две характеристики:

  1. Проблема может быть разложена на подзадачи с одной и той же идеей решения, под-подзадачи, другими словами, все эти проблемы могут вызывать одну и ту же функцию.
  2. Подзадачи, которые были декомпозированы слой за слоем, в конечном итоге должны иметь фиксированное значение, которое больше не может быть декомпозировано (то есть условие завершения), иначе подзадачи будут декомпозироваться бесконечно.

Прежде чем решать рекурсивную задачу, необходимо проверить, может ли она быть решена рекурсией по двум вышеуказанным характеристикам. После вынесения решения мы можем использовать шаблон рекурсивного решения проблем.

рекурсивная трилогия

Как я сказал выше, подумайте о трех соединениях перед рекурсией: какую проблему решает каждый уровень рекурсии? Какое должно быть возвращаемое значение после решения проблемы? Текущее условие выхода для всей рекурсии?

Кратко опишите базовую процедуру этой рекурсии.

  1. Найдите условие завершения всей рекурсии: когда должна закончиться рекурсия?
  2. Найдите возвращаемое значение: какое возвращаемое значение следует передать предыдущему уровню?
  3. Что должен делать этот уровень рекурсии: Что следует делать на этом уровне рекурсии?

Применяя эту трилогию, мы можем решить некоторые распространенные проблемы рекурсии:

Например, классическая последовательность Фибоначчи: f[n]=f[n-1]+f[n-2]. n-1 — предыдущее число, переданное в параметре n, n-2 — первые два числа, переданные в последнем параметре n, мы должны каждый раз добавлять f(n-1) и f(n-2), чтобы получить возвраты значение до тех пор, пока выход f(1)f(2) не вернет 1. Примените шаблон, чтобы уточнить, что делает каждый шаг:

  1. Конечное условие для рекурсии? f[1]=1, f[2]=1, что является подзадачей, которую можно решить с наименьшей степенью детализации,
  2. Какую информацию этот слой возвращает на верхний уровень? вернуть f(n-1)+f(n-2)
  3. Что должен делать этот уровень рекурсии? Задача каждого слоя одинакова, т.е. вычисление возвращает f[n-1]+f[n-2].

Это упрощает написание рекурсивного решения последовательности Фибоначчи.

function fn(n){
	if(n==1|n==2){
	return 1;
	}
	return fn(n-1)+fn(n-2);	
	//不断调用自身函数，n-1是传参的前一次，n-2是最后传参的前两个数字。
}

Я полагаю, что увидев это, вы более или менее в своем сердце имеете общее представление о рекурсии. При чистке вопросов, в зависимости от структуры данных: линейной или нелинейной, существуют разные методы обхода данных: линейный соответствующий цикл и итерация для (пока), истина/ложь, нелинейная рекурсия использования, вы обнаружите, что до тех пор, пока проблемы, связанные с рекурсией, - это все проблемы с деревьями. Даже если его структура данных не является деревом, ее можно абстрагировать в дерево.

Давайте начнем с самых простых задач, чтобы понять бинарные деревья и рекурсию.

Различные позы бинарного дерева

В дереве так много узлов, но структура узлов дерева одинакова.Независимо от того, сколько узлов, мы можем сделать то же самое с узлом, как показано на рисунке:

TreeNode

Структура данных узла следующая

 function TreeNode(val) {
 this.val = val;
 this.left = this.right = null;
 }

Согласно рекурсивному дизайну универсального метода алгоритма бинарного дерева ясно, что должен делать узел, а все остальное остается за этим общим методом.

В принципе, все деревья можно абстрагировать таким образом.

var traverse = function(root) {
	//这里写root要做什么，具体的代码
	//剩下节点怎么办，交给同一个方法。
	traverse (root.left)
	traverse (root.right)
}

Обход дерева имеет очевидную идею разделяй и властвуй, ведь такие коды очень распространены👇

	traverse (root.left)	//看左边
	traverse (root.right)	//看右边

Все задачи с бинарными деревьями можно разделить на два случая: смотреть налево (левое дерево) и смотреть направо (правое дерево), и решать их одну за другой. Подобно нашему общему делению пополам (низкий, высокий), задача делится пополам, чтобы решить вот так. Пока размер дивизии не уменьшится до простого решения.

Некоторые распространенные вопросы по алгоритму бинарного дерева

Сначала самое простое 😏

как добавить один ко всем узлам в бинарном дереве

var plusOne= function(root) {
	if (root === null) return;
	root.val += 1;	//当前root要做的操作
	plusOne (root.left);
	plusOne (root.right);
}

Таким же образом можно добавить единицу к узлам в левом и правом деревьях, и дерево будет пустым (null) для выхода из цикла.

Следующие темы являются оригинальными темами LeetCode. Я даю только краткое описание тем. Рекомендуется щелкнуть ссылку, которую я разместил, чтобы перейти на LeetCode, чтобы увидеть исходные темы.

сравнивает два дерева на равенство

ссылка LeetCode

var isSameTree = function(p, q) {
  if(!p && !q) return  true;	//都为空，显然相同
  if(!p || !q) return  false;	//一个为空，一个非空，不同步，显然不同
  if(q.val !== p.val) return  false;	//结点value不一样，不同
//上面即要对每个节点做的操作，返回值是true|false，接下来就是递归判断左右树
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); //p,q 两个子树，分别比较两个子树
};

Решение о равенстве этого дерева не должно изменять значение дерева, ему нужно только перечислить все случаи, которые делают дерево неравным, вернуть false, если оно исключено, и, наконец, вернуть логическое значение.

зеркальное отображение бинарного дерева

ссылка LeetCode

Набор шаблонов решений:

  1. Найдите условие завершения.Когда заканчивается рекурсия? Дерево пусто (null) и рекурсия заканчивается.
  2. Найдите возвращаемое значение.Что следует вернуть? Возвращает текущий узел после замены левого и правого поддеревьев
  3. Что должен делать этот уровень рекурсии.После обмена сбросить текущие левое и правое поддеревья, то есть вызвать ту же функцию обмена, вернуть обмененный узел и сбросить исходное бинарное дерево.
var mirrorTree = function(root) {
// 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点 null返回
    if(!root) return null
    //交换结点
    let temp = root.left
    root.left = root.right
    root.right = temp
    // 重复对左右子树做一样的操作，并重置root
    root.left = mirrorTree(root.left)
    root.right = mirrorTree(root.right)

    return root
};

Найдите максимальную глубину бинарного дерева

ссылка LeetCode

Примените шаблон решения проблемы:

  1. Найдите условие завершения.Когда заканчивается рекурсия? Дерево пусто (null) и рекурсия заканчивается.
  2. Найдите возвращаемое значение.Что следует вернуть? Задача состоит в том, чтобы найти максимальную глубину дерева, нам нужно вернуть максимальную глубину левого и правого поддеревьев в соответствии с глубиной +1, пройденной каждым слоем.
  3. Что должен делать этот уровень рекурсии.Прежде всего, еще подчеркивается, чтобы выйти из предыдущего недоразумения.Каждый узел имеет три рабочих значения: корень, корень.левый, корень.право.Согласно второму шагу, левый и правый соответственно записывают левое и правое поддеревья дерева корень максимальная глубина. Мы обновляем это значение каждый раз, когда переходим к новому узлу, а затем возвращаемся к большей глубине слева и справа.
var maxDepth = function(root) {
	if(root === null){
		return  0;
	}
	let lefth = maxDepth(root.left)
	let righth = maxDepth(root.right)
	return  Math.max(lefth, righth) + 1
};

В настоящее время мы обнаружили, что два приведенных выше вопроса касаются тольковозвращаемое значение, и это возвращаемое значение находилось в процессе обхода узлавозобновить, Если бинарное дерево включает в себя глобальные переменные, такие как кратчайший и лучший, оно не только оценивает текущий отдельный узел бинарного дерева, но также оценивает, удовлетворяет ли глобальное бинарное дерево определенному условию, и возврата возвращаемого значения явно недостаточно. , Что мне теперь делать?

С помощью функции помощи

helpFunction - это функция, которая отделяет функцию. Когда проблема сложная, возвращаемое значение не может удовлетворить наши потребности. Нам нужно больше переменных для записи текущего значения, чтобы гарантировать, что это значение может быть зафиксировано относительно глобального, а не обновляться каждый раз узел пройден.

В настоящее время функция helpFunction необходима для расширения списка параметров, определения интерфейса возвращаемого значения и передачи более полезной информации в возвращаемом значении.

Эта концепция аналогична концепции функционального программирования.Объединение параметров, который направляет вывод одного вызова функции на вызов другой функции и т. д. этодекларативныйреферат, чтобы получитьбольше информации.

Проверка сбалансированного двоичного дерева

ссылка LeetCode

Наиболее типичным является 104 вопроса для проверки сбалансированного двоичного дерева (сбалансированное двоичное дерево, называемое AVL).

BSTandAVL

Определение сбалансированного бинарного дерева: Абсолютное значение разницы высот между левым и правым поддеревьями каждого узла бинарного дерева не превышает 1.

На данный момент нам недостаточно записать текущую высоту, потому что это требует не только того, чтобы разница высот между нашими текущими левым и правым поддеревьями не превышала 1, но и разница высот всего дерева не могла превышать 1.

Таким образом, нам нужно как минимум два возврата:

  1. текущая высота узла
  2. Является ли текущий узел сбалансированным бинарным деревом

Если текущий узел не является сбалансированным двоичным деревом, что еще осталось пройти == , просто верните false

   var isBalanced = function (root) {
      // 传任意结点，返回当前节点的高度
      function height(node) {
        if (node === null) {
          return 0; //叶子结点，返回null
        }
        let h = Math.max(height(node.left), height(node.right)) + 1; //递归 在左右子树选较大高度值，加一即当前结点高度
        return h;
      }
      if (!root) return true; //该树没有任何叶子结点，即为平衡二叉树
      // 判断高度差绝对值是否超过1，且要递归判断每个节点的子树
      return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right)
    };

используется здесьheightФункция helpFunction. helpFunction называется в соответствии с тем, что вы хотите сделать. На макроуровне его роль состоит в том, чтобы предоставить вспомогательной функции более полезные параметры.

Чтобы понять роль helpFunction, давайте рассмотрим другие сценарии реализации:

Иерархический обход бинарного дерева

ссылка LeetCode

Описание темы: Учитывая бинарное дерево, возвращайте значения его узлов, пройденные иерархически. (т.е. слой за слоем, посещая все узлы слева направо). Например

    3
   / \
  9  20
    /  \
   15   7
   
  返回[ [3],[9,20],  [15,7] ]

Здесь нам, очевидно, нужно использовать helpFunction, потому что то, что мы в конечном итоге возвращаем, определенно является двумерным массивом, но текущий обход осуществляется поуровеньОбход, сам узел может оперировать только своими левым и правым поддеревьями, поэтому необходима функция длязаписывать узлы текущего уровня, сохраните его как одномерный массив; запишите сравнение текущего количества слоев с общим количеством слоев, которые необходимо обновить.

//二叉树的层次遍历
var levelOrder = function(root) {
  let levels = []	//最后返回总的二维数组
  if(!root) {
    return levels	//空树返回空数组
  }
  function walk(node, level) {
    if(levels.length === level) {//新的层级
      levels.push([])
    }
    levels[level].push(node.val)	//保存当前结点
    if(node.left) {
      walk(node.left, level + 1)	//level+1 向下层遍历
    }
    if(node.right) {
      walk(node.right, level + 1)
    }
  }
  walk(root, 0)
  return levels;
}

Суждение бинарного дерева поиска (BST)

ссылка LeetCode

бинарное дерево поиска(сокращенно BST) — очень часто используемое бинарное дерево, которое определяется как: в бинарном дереве значение любого узла больше, чем значение всех узлов в левом поддереве, и меньше или равно значению все узлы в правом поддереве: Цифра - это BST, который должен соответствовать определению

BST

Подобно дереву AVL, текущий корень узла должен не только сравнивать левый и правый узлы, но и сравнивать все левое поддерево и все узлы правого поддерева Одного возвращаемого значения определенно недостаточно, и на этот раз необходимо разработать helpFunction

var isValidBST = function (root) {
	let inOrderList = [];

	function inOrder(node) {
		if (!node) return;
		inOrder(node.left);	//判断左树
		inOrderList.push(node.val);
		inOrder(node.right);  //判断右树
	}
	// 从根节点开始遍历 返回结点数组
	inOrder(root)
	for (let i = 0; i < inOrderList.length - 1; i++) {
		// 确保遍历出的结点是递增 ==> 平衡树
		if (inOrderList[i] >= inOrderList[i + 1]) { //考虑结点相等的情况！
		return  false
		}
	}
return  true
};

резюме

Увидев здесь, вы должны изучить следующие навыки

  1. Принцип алгоритма бинарного дерева: делайте то, что должен делать текущий узел, а остальное оставьте рекурсивной структуре, не беспокоясь о текущем узле.
  2. Если текущий узел будет иметь общее влияние на следующие дочерние узлы, вы можете разработать интерфейс возвращаемого значения с помощью вспомогательной функции helpFunction, чтобы передавать больше параметров для передачи информации.
  3. Методы проверки для деревьев BST и AVL

Расширение BFS и DFS

В предыдущей статье я сказал: любая нелинейная структура данных, включающая рекурсию, является проблемой дерева, даже если ее структура данных не является деревом, ее можно абстрагировать в дерево. Далее мы обсудим задачу решения графов в глубину и в ширину, та же идея, тот же метод.

стратегия поиска в глубину

Сначала определите понятие

Поиск в глубину (DFS): алгоритм обхода или поиска по дереву или графу. Обход узлов дерева по глубине дерева, поиск ветвей дерева как можно глубже. Когда ребра узла v были исследованы или узел не удовлетворяет условиям во время поиска, поиск вернется к начальному узлу ребра, где найден узел v. Весь процесс повторяется до тех пор, пока не будут посещены все узлы. Он относится к слепому поиску, а временная сложность алгоритма в наихудшем случае составляет O(!n).

источниквики поиск в глубину

Метод поиска с возвратом: разновидность оптимального метода поиска, также известного как эвристический метод.

在危险的边缘疯狂试探
试探之后

Дело в том,Если не подходит, вернитесь к предыдущему шагу

Общие шаблоны решения проблем для поиска с возвратом

result = []
function backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 of 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

Но при этом в худшем случае временная сложность поиска с возвратом станет больше, поэтому необходимо использоватьобрезкачтобы ускорить.обрезкаиспользуется в процессе поискафильтрОтрежьте пути поиска, которые вообще не учитываются (было решено, что оптимальное решение не может быть получено, идя по этой дороге), тем самым избегая некоторых ненужных поисков. Обрезка — это очень образ для описания, представьте, что когда наступит весна, дядя-садовник срежет все нисходящие ветви дерева, оставив восходящие. Это обрезка.

Если конкретно спрашивать о количестве решений, спрашивайте оптимальное, первое и кратчайшее, вообще говоря, используйте для этого dp, а спрашивайте множество всех решений, используйте DFS

Шаблон ДФС

result： 所有结果集
list： 当前的单个解	（result和list会在DFS的过程中不断更新）
pos：记录当前处理的位置
visited：结点有无访问状态（求最优路径）
if(condition) 退出条件

Возьмем в качестве примера вопрос средней сложности dfs.

Набор всех допустимых скобок

ссылка LeetCode

Описание темы: Разработайте алгоритм, который выводит все допустимые (например, взаимно-однозначные) комбинации n пар скобок. И набор решений не может содержать повторяющиеся подмножества. Например, при n = 3 результирующий результат:

[ "((()))", "(()())", "(())()", "()(())","()()()" ]

Этот вопрос, очевидно, должен возвращать набор решений всех допустимых круглых скобок Интерфейс возвращаемого значения, который должен быть возвращен helpFuncton (DFS в решении), включает в себя (текущую оставшуюся левую круглую скобку, оставшуюся правую круглую скобку, текущую допустимую левую/правую круглую скобку , коллекция результатов). И тут всего два случая, добавить текущий список или нет.

Спасибо за мнения копателей в комментариях, я нарисовал все допустимые ситуации, надеюсь, это поможет всем понять. Картина немного некрасивая, пожалуйста, потерпите меня 😥😥😥

function dfs(left, right, list, result){
	if(left === 0 && right === 0){ // 左右括号都为0，退出条件
		result.push(list)
	}
	// dfs只有两种情况，加入list或不加，提前判断加入括号是否有效
	if(left > 0){ //左括号无所谓增加 有就放
		dfs(left - 1, right, list + '(', result) //放入哪边括号 剩余n -1
	}

	//已有的左括号>右括号才能放入，即剩下的左括号<右括号
	if(left < right){
		dfs(left, right - 1, list + ')', result)
	}
}
var generateParenthesis = function(n) {
	let result = [];
	let list = '';
	// 已知n，不需要记录当前visited来判断退出条件
	dfs(n, n, '', result);
	return result;
};

Поскольку этот вопрос дает условие завершения, то есть n пар круглых скобок, нет необходимости судить, заполнен ли он, поэтому нет необходимости записывать и судить о текущем посещении.

И здесь используется при оценке действительногообрезкаИдея: потому что некоторые DFS генерируют решения для всех случаев, а затем судят, является ли оно допустимым или нет, при оценке условий выхода;

Однако перед добавлением текущего списка мы оцениваем, допустимы ли левая и правая круглые скобки, и помещаем их в результат только в том случае, если они удовлетворены, чтобы гарантировать, что когда длина (n) подходит для выхода из цикла, полученные результаты являются допустимыми решениями.

стратегия в ширину

BFS: от корневого узла по ширине дерева каждый разузлы доступа на одном уровне, если посещен тот же слой, то посетить следующий слой, если посещены все узлы, алгоритм завершается, и путь, найденный BFS, является кратчайшим путем.

По сравнению с DFS, DFS - это путь до конца, и здесь нет последовательности, BFS проходит по уровням, чтобы записывать текущий уровень обхода, что более способствует поиску оптимального пути.

гнилые апельсины

ссылка LeetCode

Описание предмета: В данной сетке есть три возможных значения: 0 для пустых ячеек, 1 для свежих апельсинов, 2 для гнилых апельсинов. Каждую минуту любой свежий апельсин, соседствующий с гнилым апельсином (в 4 положительных направлениях), будет гнить. Возвращает минимальное количество минут, которое должно пройти, пока в ячейке не останется свежих апельсинов.

Гнилой апельсин должен быть упрощенной версией задачи о королеве N. Нет необходимости возвращать набор решений, находить минимальное время, и каждый апельсин гниет в четырех направлениях каждого слоя.Уровень первый, и считается BFS .

Рекурсия не используется. план: перечисление + BFS

Интерпретируйте тему и сопоставьте ее с концепцией BFS:

  • Смежные в четырех направлениях --> посетить один и тот же слой узлов
  • Загрязните узлы в четырех направлениях --> выполните BFS для каждого плохого апельсина.
  • Кратчайший путь --> кратчайшее время затухания

Тем не менее оригинальный шаблон.

result： 所有结果集
list： 当前的单个解	（result和list会在DFS的过程中不断更新）
pos：记录当前处理的位置
visited：结点有无访问状态（求最优路径）
if(condition) 退出条件

В список записываются координаты текущего плохого апельсина и прошедшее время, которое необходимо вернуть в конце, а двумерные координаты записывают текущее направление движения вперед.

var orangesRotting = function(grid) {
	// 1. 初始化坏橘坐标，好橘个数，经过时间，
	let time = 0;
	let result = [];
	let foc = 0; //fresh orange count = 0
	for(let i=0; i<grid.length; i++){
	for(let j=0; j<grid[i].length; j++){
		if(grid[i][j] === 2) result.push([i, j ,0])
		if(grid[i][j] === 1) foc++;
		}
	}
	console.log(result, foc)
	// 开始遍历队列中的坏橘
	while(result.length){
		let cur = result.shift();
		console.log(cur)
		time = cur[2];//腐烂时间
		rotting(cur[0], cur[1], cur[2]);
	}
	// 处理腐烂感染过程
	function rotting(row, col, time){
		let direction = [[-1,0], [0,1], [1,0], [0,-1]]; //先四	个方向（广度）遍历
		for(let d=0; d<4; d++){
		let r = row + direction[d][0];
		let c = col + direction[d][1]; //当前坐标向四个方向移动
		// 在gird内且是新鲜可感染的橘子，置2; 否则continue
		if(r<0 || r>=grid.length || c<0 || c>=grid[0].length || grid[r][c] !== 1) {continue} else {
		grid[r][c] = 2;
		foc --;
		result.push([r, c, time+1])
		}
	}
}
// 最后所有橘子都一定会坏,否则就没有坏橘
return foc > 0 ? -1 : time
};

Суммировать

  • Прочитав эту статью, вы поймете основные идеи и способы использования основных идей алгоритмов, таких как рекурсия, разделяй и властвуй, обрезка, поиск с возвратом, перечисление, DFS и BFS.
  • Идея состоит в том, чтобы освоить решения распространенных проблем с бинарными деревьями.
  • Статья очень длинная, с более чем 10 000 слов, картинок и текстов. Вы можете поставить лайк, добавить в избранное и читать медленно.
  • Я так долго нырял в сообществе. Я очень благодарен за техническое разделение больших парней на Наггетс. По пути я помог мне, маленькому белому в школе, многому научиться. Я также надеюсь что я могу писать хорошие статьи, чтобы поделиться с сообществом и подвести итоги своей недавней работы.То, что вы узнаете, может помочь вашим коллегам-диггерам. Наггетсы похожи на облака, а беленький вроде меня тоже пугается при публикации. Если что-то не так с тем, что я написал, пожалуйста, дайте мне знать в области комментариев, и я с нетерпением жду общения с вами~🤣🤣🤣
Категории