Що робить postorder traversal (постфіксний обхід дерева)?

АлгоритмиJunior~1 хв читання

Коротка відповідь

Postorder traversal (постфіксний обхід) - це поглиблений обхід дерева, який відвідує вузли в порядку: ліве піддерево, праве піддерево, сам вузол (L-R-Root). Для n-арного дерева - усі діти зліва направо, потім вузол.

Детальне пояснення

Постфіксний обхід - одна з форм обходу в глибину (DFS). Головна ідея: спочатку повністю обробити піддерева, а потім поточний вузол. Це робить postorder природним вибором для задач, де значення вузла залежить від результатів його нащадків.

Порядок обходу (бінарне дерево): ліве піддерево, праве піддерево, вузол (L-R-Root).
Для n-арного дерева: обійти всіх дітей зліва направо, потім поточний вузол.
Складність: час O(n), пам'ять O(h) при рекурсії (h - висота дерева). Ітеративні версії використовують O(h) додаткової пам'яті для стека.
Де корисний: обчислення значень у дереві виразів (отримання постфіксної форми), видалення/звільнення дерева знизу вгору, обчислення розмірів/висот піддерев, серіалізація в обернений польський запис.

Приклад на дереві

      A
     / \
    B   C
   / \
  D   E

Постфіксний порядок: D, E, B, C, A

Рекурсивна реалізація (JavaScript)

// Вузол бінарного дерева
// { val: any, left: Node|null, right: Node|null }

function postorderRecursive(node, visit) {
  if (!node) return;
  postorderRecursive(node.left, visit);
  postorderRecursive(node.right, visit);
  visit(node);
}

// Приклад
const tree = {
  val: 'A',
  left: {
    val: 'B',
    left: { val: 'D', left: null, right: null },
    right: { val: 'E', left: null, right: null }
  },
  right: { val: 'C', left: null, right: null }
};

const result = [];
postorderRecursive(tree, n => result.push(n.val));
console.log(result); // ['D', 'E', 'B', 'C', 'A']

Ітеративна реалізація (JavaScript, без рекурсії)

Однoстековий підхід з покажчиком на останній відвіданий вузол. Рухаємось вліво, потім перевіряємо правого нащадка і вирішуємо, спускатися чи відвідувати вершину.

function postorderIterative(root, visit) {
  const stack = [];
  let lastVisited = null;
  let curr = root;

  while (stack.length || curr) {
    if (curr) {
      stack.push(curr);
      curr = curr.left;
    } else {
      const peek = stack[stack.length - 1];
      if (peek.right && lastVisited !== peek.right) {
        curr = peek.right;
      } else {
        visit(peek);
        lastVisited = stack.pop();
      }
    }
  }
}

// Перевірка
const out = [];
postorderIterative(tree, n => out.push(n.val));
console.log(out); // ['D', 'E', 'B', 'C', 'A']

N-арне дерево

У n-арному дереві вузол має масив children. Ми обходимо всіх дітей зліва направо, потім відвідуємо поточний вузол:

// Вузол n-арного дерева: { val, children: Node[] }
function postorderNAry(node, visit) {
  if (!node) return;
  for (const child of node.children || []) {
    postorderNAry(child, visit);
  }
  visit(node);
}

// Приклад структури:
const nary = {
  val: 'A',
  children: [
    { val: 'B', children: [ { val: 'E', children: [] }, { val: 'F', children: [] } ] },
    { val: 'C', children: [] },
    { val: 'D', children: [] }
  ]
};

const order = [];
postorderNAry(nary, n => order.push(n.val));
console.log(order); // ['E', 'F', 'B', 'C', 'D', 'A']

Типові задачі, де потрібен постфіксний обхід

Дерева виразів: обчислення значення і генерація оберненого польського запису.
Видалення/звільнення дерева: спочатку звільняємо нащадків, потім батька.
Підрахунок властивостей піддерев: розміри, висоти, суми значень.
Серіалізація/копіювання, коли порядок «знизу вгору» критичний.

Граничні випадки і зауваження

Порожнє дерево: обхід нічого не робить.
Один вузол: повертається сам корінь.
Сильно незбалансоване дерево: глибина рекурсії може досягати O(n); за ризику переповнення стека використовуйте ітеративний варіант.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.