Aby wydrukować granicę drzewa binarnego

Question

Zostałem poproszony w wywiadach, aby wydrukować granicę drzewa binarnego. Na przykład.

 1 
/ \ 
    2  3 
/\ /\ 
4 5 6 7 
    / \  \ 
    8  9  10 

odpowiedź będzie: 1, 2, 4, 8, 9, 10, 7, 3

daję następującą odpowiedź.

Pierwsza metoda:

Użyłem zmienną Bool rozwiązać powyższy problem.

void printLeftEdges(BinaryTree *p, bool print) { 
    if (!p) return; 
    if (print || (!p->left && !p->right)) 
     cout << p->data << " "; 
    printLeftEdges(p->left, print); 
    printLeftEdges(p->right, false); 
} 

void printRightEdges(BinaryTree *p, bool print) { 
    if (!p) return; 
    printRightEdges(p->left, false); 
    printRightEdges(p->right, print); 
    if (print || (!p->left && !p->right)) 
    cout << p->data << " "; 
} 

void printOuterEdges(BinaryTree *root) { 
    if (!root) return; 
    cout << root->data << " "; 
    printLeftEdges(root->left, true); 
    printRightEdges(root->right, true); 
} 

Jego odpowiedź: Użyłeś Bool zmiennej tak wiele razy. Czy potrafisz rozwiązać to bez użycia tego.

Druga metoda:

po prostu stosować przechodzenie drzewa, aby rozwiązać ten problem.

1. Print the left boundary in top-down manner. 
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts: 
    2.1 Print all leaf nodes of left sub-tree from left to right. 
    2.2 Print all leaf nodes of right subtree from left to right. 
3. Print the right boundary in bottom-up manner. 

Jego odpowiedź: Nie był zadowolony z tej metody. Powiedział, że jesteś przemierza drzewo 3 razy. To za dużo. Daj inne rozwiązanie, jeśli je posiadasz.

Trzecia metoda: Tym razem poszliśmy do przechodzenie Level kolejności (BFS).

1: Print starting and ending node of each level 
2: For each other node check if its both the children are <b>NULL</b> then print that node too. 

Jego odpowiedź: Nie był zadowolony z tej metody, ponieważ ta metoda wymaga dodatkowej pamięci O (n).

Moje pytanie brzmi: Powiedz mi metodę, która przemierza drzewo jeden raz, nie używaj żadnej zmiennej Bool i nie używaj dodatkowej pamięci. Czy to możliwe?

Answer 1

Myślę, że to powinno wystarczyć:

traverse(BinaryTree *root) 
{ 
    if (!root) return; 
    cout << p->data << " "; 
    if (root->left) traverseL(root->left); //special function for outer left 
    if (root->right) traverseR(root->right); //special function for outer right 
} 

traverseL(BinaryTree *p) 
{ 
    cout << p->data << " "; 
    if (root->left) traverseL(root->left); //still in outer left 
    if (root->right) traverseC(root->right); 
} 

traverseR(BinaryTree *p) 
{ 
    if (root->left) traverseC(root->left); 
    if (root->right) traverseR(root->right); //still in outer right 
    cout << p->data << " "; 
} 

traverseC(BinaryTree *p) 
{ 
    if (!root->left && !root->right) //bottom reached 
    cout << p->data << " "; 
    else 
    { 
    if (root->left) traverseC(root->left); 
    if (root->right) traverseC(root->right); 
    } 
} 

Start z funkcją traverse. Pozbyłem się kwerend zerowych na początku każdej metody (unikałem jednego wywołania funkcji na każdym końcu). Nie trzeba zmienne bool, po prostu wykorzystuje trzy różne metody przemierzania:

• jeden na lewej krawędzi, wyprowadzanie węzeł przed przechodzenie
• jeden dla prawego brzegu, wyprowadzanie węzeł po przechodzenie
• jednym dla wszystkie inne węzły, wyprowadzając węzeł, jeśli nie ma rodzeństwa.

Answer 2

Poniżej znajduje się rekurencyjne rozwiązanie w języku Python3 o złożoności czasowej O (n). Algorytm tutaj służy do drukowania lewej większości węzłów od góry do dołu, węzłów liści od lewej do prawej i prawej większości węzłów od dołu do góry. Dodawanie flag logicznych (isLeft,isRight) dla lewego i prawego drzewa upraszcza kod i steruje złożonością czasu O (n).

#Print tree boundary nodes 
def TreeBoundry(node,isLeft,isRight): 
    #Left most node and leaf nodes 
    if(isLeft or isLeaf(node)): print(node.data,end=' ') 
    #Process next left node 
    if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False) 
    #Process next right node 
    if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True) 
    #Right most node 
    if(isRight and not isLeft and not isLeaf(node)):print(node.data,end=' ') 

#Check is a node is leaf 
def isLeaf(node): 
    if (node.getLeft() is None and node.getRight() is None): 
     return True 
    else: 
     return False 

#Get started 
#https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py 
TreeBoundry(root,True,True) 

Answer 3

Sposób O(n) No extra space and single traversal of tree.

że podzielony drzewie węzłów na cztery typy węzłów

typ 1 -> Węzły stanowiące lewą granicę (na przykład 8)

Typ 0 -> Węzły które nie tworzą boundar (np 12)

typ 3 -> Węzły, które tworzą właściwą granicę (na przykład 22)

liści węzły (np 4,10,14)

W moim metoda jestem po prostu robi metodę recurrsion z przechodzenia drzewa (tylko modyfikowanego), gdzie moja funkcja jest tej postaci

void recFunc(btNode *temp,int type) 
    { 
     //Leaf Nodes 
    if((temp->left == NULL)&&(temp->right == NULL)) 
       cout << temp->data << " "; 
    // type -1 Nodes must be printed before their children 
    else if(type == 1)cout << temp->data << " "; 
    else {;} 


    if(type == 3) 
    { 
    if(temp->left)recFunc(temp->left,0); 
    if(temp->right)recFunc(temp->right,3); 
    //type 3 nodes must be printed after their children 
    cout << temp->data << " "; 
    } 
    else if(type == 1) 
    { 
    if(temp->left)recFunc(temp->left,1); 
    if(temp->right)recFunc(temp->right,0); 
    } 
    else if(type == 0) 
    { 
    if(temp->left)recFunc(temp->left,0); 
    if(temp->right)recFunc(temp->right,0); 
    } 
    else {;} 
    } 

gdzie mam modofied

1. W moim recurrsive funkcji węzłach typu 1 musi dokonać ich lewej węzły jako typ 1 i muszą być wydrukowane przed wywołaniem swoje dzieci (jeśli istnieją)
2. węzły typu 3 muszą być drukowane w odwrocie kolejność .Tak muszą być drukowany po wywołaniu ich children.They należy również przypisać ich prawo dzieci jako typ 3 Węzły
3. węzłach Typ 0 nie muszą być drukowane i przypisanie ich dzieci jak typu 0 węzłów
4. liści Węzły musi być bezpośrednio drukowane tylko i powrócić

Link to Code