145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

return [3, 2, 1].

Recursive solution is trivial, could you do it iteratively?

145. Обратный порядок обхода бинарного дерева

Дано бинарное дерево. Вернуть обратный порядок обхода его вершин.

вернет [3, 2, 1].

Рекурсивное решение тривиально. Приведите итеративное решение.

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

}

};

РЕШЕНИЕ

структуры данных - дерево

Анализ алгоритма

1. Положить корень дерева в первый стек

2. Пока первый стек не пустой

а) извлекаем вершину из первого стека и заносим ее во второй;

б) заносим в первый стек левого и правого сына этой вершины;

3. Извлекаем и выводим на печать элементы второго стека.

Пример

Рассмотрим порядок обхода дерева на примере:

PostOrder: 3, 6, 4, 12, 24, 16, 9.

Реализация алгоритма

class Solution

{

public:

vector<int> postorderTraversal(TreeNode *root)

{

vector<int> res;

if (root == NULL) return res;

stack<TreeNode *> s;

stack<TreeNode *> output;

s.push(root);

while(!s.empty())

{

TreeNode *node = s.top(); s.pop();

output.push(node);

if (node->left != NULL) s.push(node->left);

if (node->right != NULL) s.push(node->right);

}

while(!output.empty())

{

res.push_back(output.top()->val);

output.pop();

}

return res;

}

};