Cree un Árbol de Búsqueda Binario Equilibrado dado una lista ordenada pasando la lista al método de clasificación en Python.
Como indica el título, mi objetivo es imprimir el recorrido en preorden del Árbol de Búsqueda Binaria Equilibrado a partir de una lista ordenada (de forma ascendente).
Las restricciones son las siguientes:
– sortedarrayto_bst() tiene que ser un método de la clase TreeNode.
– Este método recibe como argumento la lista ordenada (no los elementos de la lista iterativamente).
“`
class TreeNode(object):
def <strong>init</strong>(self, x=None):
self.val = x
self.left = None
self.right = None
<pre><code>def sorted_array_to_bst(self, nums):
def srt(nums):
if not nums:
return None
mid_num = len(nums) // 2
if self.val is None:
self.val = nums[mid_num]
# if self.val == nums[mid_num]:
self.left = TreeNode(nums[:mid_num])
self.right = TreeNode(nums[(mid_num + 1):])
if self.val is None:
srt(nums)
def preorder(self, val):
if self.val is not None:
val.append(self.val)
if self.left is not None:
self.left.preorder(val)
if self.right is not None:
self.right.preorder(val)
return val
</code></pre>
node = TreeNode()
some<em>list = [1, 2, 3, 4, 5, 6, 7]
node.sorted</em>array<em>to</em>bst(some_list)
print(node.preorder([]))
“`
Por ahora, el resultado es:
[4, [1, 2, 3], [5, 6, 7]]
Tiene que ser:
[4, 2, 1, 3, 6, 5, 7]
He intentado ordenar la mitad izquierda y derecha de la lista:
self.left = TreeNode(srt(nums[:mid_num]))
self.right = TreeNode(srt(nums[(mid_num + 1):]))
pero el resultado es solo [4]
davy.ai
Para imprimir la preorden del Árbol Binario de Búsqueda Equilibrado a partir de una lista ordenada (ascendentemente), se puede utilizar el siguiente enfoque:
sorted_array_to_bst()
dentro de la claseTreeNode
que tome una lista ordenadanums
como argumento.sorted_array_to_bst()
, definir una función auxiliarbuild_tree()
que tome como argumentos un índice inicialstart
y un índice finalend
.start
es mayor que el índiceend
, devolverNone
ya que esto significa que hemos llegado al final del árbol.mid = (start + end) // 2
, y crear un nuevo objetoTreeNode
con el valornums[mid]
.build_tree()
con la mitad izquierda de la lista:build_tree(start, mid - 1)
, y establecer el nodo devuelto como el hijo izquierdo del nodo actual.build_tree()
con la mitad derecha de la lista:build_tree(mid + 1, end)
, y establecer el nodo devuelto como el hijo derecho del nodo actual.build_tree()
constart = 0
yend = len(nums) - 1
para construir todo el árbol a partir de la lista ordenada dada.preorder()
dentro de la claseTreeNode
que tome una lista vacía llamadaresult
como argumento.None
, agregar su valor aresult
.preorder()
en el hijo izquierdo del nodo actual.preorder()
en el hijo derecho del nodo actual.result
.Aquí está el código que implementa el enfoque anterior:
Ahora, probemos nuestra función con el ejemplo proporcionado:
Salida:
La salida es la preorden esperada del Árbol Binario de Búsqueda Equilibrado dado la lista ordenada
[1, 2, 3, 4, 5, 6, 7]
.