[Вопрос-кисть] Нерекурсивный обход бинарного дерева

интервью Java алгоритм

Ссылка на оригинальное название:

вся идея

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

  1. Разделите бинарное дерево на два узла: «левый» (включая весь путь влево, все фактические левые + корни, которые проходят) и «правый» (включая фактический правый)
  2. Поместите «левый» узел в стек в том же порядке.
  3. Поверните в нужное время (после поворота «правый» узел становится «левым» узлом), посетите узел или вытащите стек

Например, {1,2,3}, когда cur находится в узле 1, 1 и 2 принадлежат "левому" узлу, а 3 принадлежит "правому" узлу. Нерекурсивная реализация DFS, по сути, координирует порядок трех операций: push, pop и access. Вышеупомянутая унификация заставляет нас больше не сосредотачиваться на порядке укладки, а только на извлечении и доступе (пункт 3).При более детальном анализе вы оцените преимущества этого упрощения.

Доступ к узлу определяется какresults.add(node.val);, проанализируйте, как показано ниже:

Предзаказ && По порядку:

Предзаказ и заказ очень похожи.

  • Фактический порядок предварительного заказа: корень слева и справа
  • Фактический порядок: левый корень правый

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

Это дает нам интуитивное ощущение, что код будет похожим. На самом деле это так, разница между preorder и inorder только в доступе к "левому" узлу.

реализация предзаказа

Нет необходимости заталкивать в стек, каждый раз, когда вы переходите к «левому» узлу, вы можете сразу его вывести.

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

while (cur != null) {
	results.add(cur.val);
	stack.push(cur);
	cur = cur.left;
}

Затем, поскольку мы уже посетили все «левые» узлы, нам просто нужно вытолкнуть бесполезные узлы из стека и перейти к «правильному» узлу. Таким образом, «правый» узел также становится «левым» узлом, и последующая обработка такая же, как описано выше.

if (!stack.empty()) {
	cur = stack.pop();
	// 转向
	cur = cur.right;
}

Полный код выглядит следующим образом:

private List<Integer> dfsPreOrder(TreeNode root) {
	ArrayList<Integer> results = new ArrayList<>();
	Stack<TreeNode> stack = new Stack<>();

	TreeNode cur = root;
	while (cur != null || !stack.empty()) {
		while (cur != null) {
			results.add(cur.val);
			stack.push(cur);
			cur = cur.left;
		}
		cur = stack.pop();
		// 转向
		cur = cur.right;
	}

	return results;
}

Реализация среднего порядка

На основании анализа прецедента,先序与中序的区别只在于对“左”节点的处理上, мы можем изменить одну строку кода, чтобы выполнить обход по порядку.

while (cur != null) {
	stack.push(cur);
	cur = cur.left;
}
cur = stack.pop();
results.add(cur.val); // 仅调整该行代码
// 转向
cur = cur.right;

Обратите внимание, что мы не получаем доступ к этому узлу до тех пор, пока не вытолкнем стек. Потому что предварительный порядок сначала посещает фактический корень, затем фактический левый, а неупорядоченный — прямо противоположный. То же, что после посещения корня + левого поддерева (по порядку) или левого поддерева + корня (по порядку) нужно обратиться к "правильному" узлу, чтобы "правый" узел назвали новым" левый" узел.

Полный код выглядит следующим образом:

private List<Integer> dfsInOrder(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        results.add(cur.val);
        cur = cur.right;
    }
    return results;
}

пост-заказ

Пост-процедура немного отличается, но все же довольно лаконична.

  • Фактический порядок обратного порядка: левый и правый корни

Порядок укладки неизменен, нужно только учесть изменение в пункте 3 (合适时机转向). Все объекты, извлеченные из стека, должны быть «левыми» узлами («правые» узлы будут называться «левыми» узлами после поворота, а затем помещаться в стек), то есть фактически левыми или корневыми; фактически левые могут следует рассматривать как левое и правое поддеревья.нулевой корень, поэтому нам нужно проанализировать только фактический корень.

Для фактического корня необходимо убедиться, что доступ к корню возможен только после последовательного посещения левого и правого поддеревьев. Фактический правый узел, левый узел и корневой узел станут «левыми» узлами в стеке, поэтому нам нужно толькоПеред извлечением стека обработайте узел как фактический корневой узел и проверьте, было ли посещено его правое поддерево.Вот и все. Если нужное поддерево не существует или нужное поддерево было посещено, то можно посетить корневой узел и извлечь его из стека без поворота; сначала дождитесь его посещения, а затем посетите корневой узел.

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

Полный код выглядит следующим образом:

private List<Integer> dfsPostOrder(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    
    TreeNode cur = root;
    TreeNode last = null;
    while(cur != null || !stack.empty()){
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if (cur.right == null || cur.right == last) {
            results.add(cur.val);
            stack.pop();
            // 记录上一个访问的节点
            // 用于判断“访问根节点之前，右子树是否已访问过”
            last = cur;
            // 表示不需要转向，继续弹栈
            cur = null;
        } else {
            cur = cur.right;
        }
    }
    
    return results;
}

Суммировать

Да здравствует простота мышления! Да здравствует шаблон Дафа!

Уничтожь человеческую тиранию, мир принадлежит трем телам!

Ссылка на эту статью:[Вопрос-кисть] Нерекурсивный обход бинарного дерева
автор:обезьяна 007
Источник:monkeysayhi.github.io
Эта статья основана наCreative Commons Attribution-ShareAlike 4.0Международное лицензионное соглашение выпущено, его можно перепечатать, вывести или использовать в коммерческих целях, но авторство и ссылка на эту статью должны быть сохранены.

Категории