1. дома
  2. Вопрос и ответ
  3. Зернистое двоичное дерево в постоянное время

Зернистое двоичное дерево в постоянное время

2015-10-24 4 views

ответ

4

Конечно, в зависимости от структуры данных вы просто выполняете эквивалент: вместо перехода по левому узлу, а затем по правому узлу, вы проходите по правому узлу, а затем по левому узлу. Это может быть параметр, передаваемый в рекурсивную функцию, которая пересекает дерево (т. Е. В C/C++, a bool bDoLeftFirst и оператор if, который использует этот параметр для определения того, какой порядок пересекает дочерние узлы).

источник

2015-10-24 05:36:22

+0

Разве это не O (n), поскольку вы пересекаете все дерево? OP запрашивает постоянное время –

+0

Это могут быть не левые/правые узлы, а узлы a/b, а параметр будет определять, является ли это слева или справа, следовательно, постоянное время –

+2

@ cricket_007 - я думаю, дело в том, что «зеркалирование» отдельно от обхода. Чтобы избежать аргументов педантирования, вы можете сделать часть флага типа направления структуры данных, определяя роли дочерних указателей. Это O (1) для переключения флага, поэтому O (1) переопределяет роли дочерних указателей. Все, что делает указатель left-child * be * указателем left-child - это имя и то, как вы его используете, - измените их, и нет причин, по которым роли не могут меняться во время выполнения, как определено флагом, который также является частью структура данных. – Steve314

1

Возможно, вы имели в виду «invert binary tree», проблема, которую Max Howell не смог решить и таким образом отклонил Google?

https://leetcode.com/problems/invert-binary-tree/

Вы можете найти решения в разделе "обсудить".

источник

2015-10-24 16:06:09 NMSL

+0

То, что я имел в виду, является инверсией, но не обсуждаются никакие решения O (1). – ayberkt

+0

@ayberkt Я не думаю, что вы можете сделать это в O (1). – NMSL

+0

@ayberkt Вы должны проходить по крайней мере одно подрево итеративно или рекурсивно, что занимает не менее O (h) времени. – NMSL

Смежные вопросы

 Смежные вопросы