---
title: "Быстрое решение задач обхода дерева под давлением (hack)"
description: "В посте 2008, oбходы деревьев и Microsoft Denmark я рассмотрел \"классические\" решения итеративного о..."
author: "codekrolik"
published: "2014-07-24T22:38:30+00:00"
modified: "2014-07-25T01:24:54+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/bystroe-reshenie-zadach-obhoda-dereva-pod-davleniem-hack-422698"
markdown_url: "https://yvision.kz/post/bystroe-reshenie-zadach-obhoda-dereva-pod-davleniem-hack-422698/markdown"
site_name: "Yvision.kz"
---

# Быстрое решение задач обхода дерева под давлением (hack)

> В посте 2008, oбходы деревьев и Microsoft Denmark я рассмотрел "классические" решения итеративного о...

В посте [2008, oбходы деревьев и Microsoft Denmark](http://codekrolik.yvision.kz/post/422553) я рассмотрел "классические" решения итеративного обхода бинарного дерева для различных типов обхода: preorder, inorder и postorder.

Однако, из трех алгоритмов простым и понятным является лишь preorder обход, который можно написать абсолютно бездумно. Алгоритмы для inorder и postorder обходов требуют большего времени на размышление, более вдумчивого написания кода, и, в общем, с ними больше мороки. В условиях интервью с топовой компанией вам, как правило, необходимо написать решения для двух подобных задач, затратив приблизительно 15 минут на решение каждой из них. В таких условиях чрезвычайно важно быстро и четко представить код, буквально за считанные минуты, сохранив как можно больше времени на собственно его написание на whiteboard.

Кроме того, важным аспектом является оптимальность кода. Как правило, если вопрос более-менее стандартный, спрашивают runtime и memory для представленного алгоритма. Если существует более оптимальное решение, предлагают попытаться улучшить предложенное вами.

В этом посте я предложу решения для обходов inorder и postorder, которые технически являются аналогичными "классическим" с точки зрения runtime и memory, по крайней мере в терминах большого О. При этом, написание кода совершенно аналогично написанию кода для preorder traversal; т.е. практически не составляет труда и возможно в совершенно автоматическом режиме, без мучительных размышлений.

Как стало понятно из [предыдущего поста](http://codekrolik.yvision.kz/post/422553) на эту тему, главная проблема при итеративном inorder и postorder обходе - это выяснить, в какой момент ноду из стека следует процессить, а в какой момент следует получить ее детей и добавить их вместе с родителем обратно в стек. Для этого "классические" алгоритмы используют довольно интересные способы (см. [предыдущий пост](http://codekrolik.yvision.kz/post/422553)).

Трюк, значительно облегчающий эту задачу, состоит в том, чтобы в стеке хранить не ноду, а объект-враппер вокруг нее, который бы содержал булевое поле, явным образом указывающее на то, была ли такая операция произведена в предыдущих итерациях или нет.

Для обоих случаев код при использовании такого подхода превращается в абсолютно аналогичный коду preorder-обхода, за исключением, собственно, проверок этого булевого поля.

1) Имплементация postorder:

[https://gist.github.com/codekrolik/3652eaca22c25c0f95c4](https://gist.github.com/codekrolik/3652eaca22c25c0f95c4)

2) Имплементация inorder:

[https://gist.github.com/codekrolik/9165e8df451e0b0e0d10](https://gist.github.com/codekrolik/9165e8df451e0b0e0d10)

3) Тесты

[https://gist.github.com/codekrolik/ab806962e7e381c41cbf](https://gist.github.com/codekrolik/ab806962e7e381c41cbf)

Критика: технически такое решение аналогично по времени выполнения и по памяти классическим. Однако интервьюер может осознать, что его накалывают, и попытаться найти в решении изъян, который там есть, в виде дополнительной памяти, затрачиваемой на враппер. Однако следует помнить, что

1) Время выполнения O(N),где N - кол-во нод в дереве, улучшить невозможно. На то он и полный обход дерева.

2) Поскольку для классического решения также используется stack, памяти на поддержку этой структуры затрачивается O(H), где H - высота дерева. В этом решении на каждый элемент стека добавляется враппер, пусть его размер в памяти будет C; очевидно что этот размер - константа. В таком случае, использование памяти будет O(C*H +H) = O(H), что не хуже, чем в классических алгоритмах. Имеется в виду, что in-place по памяти это все равно не сделаешь никак.

Если интервьюер будет особо анальным, он может все равно заставить переделать без врапперов, но быстрое решение можно залабать минуты так за 3, и у вас все еще останется около 10 минут, чтобы имплементировать классический подход. При этом, 2 оптимальных решения, ИМХО, лучше чем 1, а также даже если классику вы запорете (что возможно, если не повторять перед интервью), то 1 решение уж по-всякому лучше чем 0.

Но исходя из моего опыта, это решение могут просто принять после аргументации на тему time complexity и memory, и вы перейдете к следующим вопросам.

На этом я буду считать тему итеративных обходов деревьев полностью закрытой.

---

Source: [https://yvision.kz/post/bystroe-reshenie-zadach-obhoda-dereva-pod-davleniem-hack-422698](https://yvision.kz/post/bystroe-reshenie-zadach-obhoda-dereva-pod-davleniem-hack-422698)