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

Odpowiedz Nowy wątek
2019-09-08 17:56
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?

A co Byś Chciał, żeby to było? - lion137 2019-09-08 18:24
Wynik taki: [4, 5, 7] ten sam ale bez zagnieżdzeń. - przemyslowiec 2019-09-08 18:36
Wiem dlaczego u mnie jast taki a nie inny ale nie wiem jak zrobić żeby było jak chcę. - przemyslowiec 2019-09-08 18:37

Pozostało 580 znaków

2019-09-08 19:02
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ń:)


edytowany 1x, ostatnio: lion137, 2019-09-08 19:05

Pozostało 580 znaków

2019-09-08 22:28
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

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2019-09-08 22:36
0

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


To wypij jeszcze parę, to zwiększa abstrakcję odbioru :D - _13th_Dragon 2019-09-08 23:41

Pozostało 580 znaków

2019-09-08 23:43
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2019-09-08 23:44

Pozostało 580 znaków

2019-09-09 15:56
_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.

edytowany 1x, ostatnio: przemyslowiec, 2019-09-09 15:57

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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