Сложность: easy
Дан корень бинарного дерева, верните обход значений узлов в постпорядке.
Пример:
Input: root = [1,null,2,3]
Output: [3,2,1]
👨💻 Алгоритм:
1⃣Заполнение стека по стратегии право->узел->лево:
Инициируйте стек и добавьте в него корень дерева.
Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода.
2⃣Извлечение узла из стека и проверка:
Извлекайте последний узел из стека, проверяя, является ли он левым листом (узел без потомков).
Если это так, добавьте значение узла в выходной список (массив значений). Если узел имеет потомков, продолжайте выполнение стека с добавлением дочерних узлов по той же стратегии.
3⃣Повторение процесса до опустошения стека:
Если извлеченный узел не является левым листом, необходимо обработать его потомков. Для этого, верните узел и его потомков в стек в правильном порядке, чтобы следующие итерации могли корректно обработать все узлы.
Повторяйте процесс до тех пор, пока стек не опустеет, что означает завершение обхода всех узлов.
😎 Решение:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> output = new LinkedList();
Deque<TreeNode> stack = new ArrayDeque();
if (root == null) return output;
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
output.addFirst(root.val);
if (root.left != null) stack.push(root.left);
if (root.right != null) stack.push(root.right);
}
return output;
}
}Ставь 👍 и забирай 📚 Базу знаний