Given a binary tree, return all values given a certain height h.

0

Rozwiązuję zadanie jak w temacie mam nawet działadzjący kod:

class Node():
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

def valuesAtHeight(root, height):
    if root == None:
        return
    if height == 1:
        return root.value
    if root.left != None and root.right != None:
        return valuesAtHeight(root.left, height - 1), valuesAtHeight(root.right, height - 1)
    if root.left == None and root.right != None:
        return valuesAtHeight(root.right, height - 1)
    return valuesAtHeight(root.left, height - 1)

tylko wynik dostaję w takiej postaci: ((4,5), 7).
Chciałbym żeby to nie były zagnieżdzone tablice ale nie mam żadnego pomysły jak tego uniknąć, ktoś ma jakieś pomysły?

1

To Możesz spróbować tak:

def values_at_height(tree, n):
	out = []
	def helper(root, m):
		if root:
			helper(root.left, m)
			if height(root) == m:
				out.append(root.value)
			helper(root.right, m)
	if tree:
		helper(tree, n)
		return out


def height(tree):
    if tree:
        l_height = height(tree.getLeftChild())
        r_height = height(tree.getRightChild())
        if l_height > r_height:
            return l_height + 1
        else:
            return r_height + 1
    else:
        return 0

Widać co to robi: przełazi przez drzewo, liczy wysokość każdego wierzchołka i jak się zgadza to do wora. Ty Możesz mieć lepszą złożoność (u mnie jest O(nlogn)), chociaż ciężko wyczuć, bo tam się podwójnie Rekurujesz, to może być troszkę tych wywołań:)

1

Można prościej.

  1. Dodajesz do listy korzeń
  2. Licznik poziomów H=1
  3. Jeżeli H=height to koniec w tablice masz wynik
  4. Zapisujesz długość tablicy w Len
  5. Dla pierwszych Len elementów dopisujesz na koniec tablicy prawe dziecko oraz podmieniasz go na lewe dziecko
  6. Zwiększasz H
  7. Przechodzisz do pkt 3
0

Wypiłem jedno piwo (Guiness), ale chyba jestem na za niskim poziomie abstrakcji, żeby ten algorytm zrozumiec, można jaśniej?

0

To proste, po każdym obrocie pętli, tablica zawiera kolejny (cały) poziom drzewa.
Nie zapomnieć pomijać null'e

1
_13th_Dragon napisał(a):

Można prościej.

  1. Dodajesz do listy korzeń
  2. Licznik poziomów H=1
  3. Jeżeli H=height to koniec w tablice masz wynik
  4. Zapisujesz długość tablicy w Len
  5. Dla pierwszych Len elementów dopisujesz na koniec tablicy prawe dziecko oraz podmieniasz go na lewe dziecko
  6. Zwiększasz H
  7. Przechodzisz do pkt 3

Dobry pomysł, nie wpadłbym na to pewnie za szybko, dzięki.

def vath(root, height):
    level = []
    counter = 1
    level.append(root)
    while height != counter:
        n = len(level)
        for item in level:
            if item.left != None:
                level.append(item.left)
            if item.right != None:
                level.append(item.right)
        counter += 1
        level = level[n::]
    result = []
    for item in level:
        result.append(item.value)
    return result

A podzielę się gotowcem jeszcze.

1 użytkowników online, w tym zalogowanych: 0, gości: 1