Задача: 145. Binary Tree Postorder Traversal
Сложность: easy

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

Пример:

Input: root = [1,null,2,3]
Output: [3,2,1]

👨‍💻 Алгоритм:

1⃣Заполнение стека по стратегии право->узел->лево:
Инициируйте стек и добавьте в него корень дерева.
Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода.

2⃣Извлечение узла из стека и проверка:
Извлекайте последний узел из стека, проверяя, является ли он левым листом (узел без потомков).
Если это так, добавьте значение узла в выходной список (массив значений). Если узел имеет потомков, продолжайте выполнение стека с добавлением дочерних узлов по той же стратегии.

3⃣Повторение процесса до опустошения стека:
Если извлеченный узел не является левым листом, необходимо обработать его потомков. Для этого, верните узел и его потомков в стек в правильном порядке, чтобы следующие итерации могли корректно обработать все узлы.
Повторяйте процесс до тех пор, пока стек не опустеет, что означает завершение обхода всех узлов.

😎 Решение:

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> output = new List<int>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root == null)
            return output;
        stack.Push(root);
        while (stack.Count > 0) {
            root = stack.Pop();
            output.Add(root.val);
            if (root.left != null)
                stack.Push(root.left);
            if (root.right != null)
                stack.Push(root.right);
        }

        output.Reverse();
        return output;
    }
}

Ставь 👍 и забирай 📚 Базу знаний