94. Binary Tree
Inorder Traversal
Given a binary tree, return
the inorder traversal of its nodes' values.
return [1, 3, 2].
Recursive solution is trivial, could you do it iteratively?
94. Центрированный
порядок обхода бинарного дерева
Дано бинарное дерево.
Вернуть центрированный порядок обхода его вершин.
вернет [1, 3, 2].
Рекурсивное решение
тривиально. Приведите итеративное решение.
class
Solution {
public:
vector<int>
inorderTraversal(TreeNode *root) {
}
};
РЕШЕНИЕ
структуры данных - дерево
Анализ алгоритма
Текущий указатель current
устанавливаем в корень. Двигаемся к левому сыну, занося вершины в стек. Когда
установится current = NULL (достигли
листа), извлекаем из стека элемент и присваиваем его значению current. Выводим его данные, переходим в
его правого ребенка и повторяем процесс заново.
Реализация алгоритма
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> res;
if (root == NULL) return
res;
stack<TreeNode
*> s;
TreeNode *current =
root;
while(!s.empty() || current)
{
if (current)
{
s.push(current);
current =
current->left;
} else
{
current =
s.top();
s.pop();
res.push_back(current->val);
current =
current->right;
}
}
return res;
}
};
Рекурсивная реализация
class Solution
{
public:
vector<int> v;
void InOrder(TreeNode *root)
{
if (root == NULL) return;
InOrder(root->left);
v.push_back(root->val);
InOrder(root->right);
}
vector<int> inorderTraversal(TreeNode *root)
{
InOrder(root);
return v;
}
};