(1,5p) Se considera n orase, numerotate cu 1,2,..,n, unite prin m drumuri. Pentru fiecare drum se cunoaste costul deplasarii de la un oras la altul. In fiecare oras exista o bariera care blocheaza deplasarea catre un oras vecin sau intrarea in acel oras dintr-un oras vecin. Doua orase se considera vecine daca sunt unite de un drum. Cunoscandu-se pozitiile initiale ale barierei, precum si costurile mutarii fiecarei bariere dintr-un oras, de la un drum la altul(care se intersecteaza in acel oras), se cere sa se determine traseul care are costul minim, plecand dintr-un oras dat start si ajungand intr-un oras dat finis. (1,5p) Se considera n orase, numerotate cu 1,2,..,n, unite prin m drumuri. Pentru fiecare drum se cunoaste costul deplasarii de la un oras la altul. In fiecare oras exista o bariera care blocheaza deplasarea catre un oras vecin sau intrarea in acel oras dintr-un oras vecin. Doua orase se considera vecine daca sunt unite de un drum. Cunoscandu-se pozitiile initiale ale barierei, precum si costurile mutarii fiecarei bariere dintr-un oras, de la un drum la altul(care se intersecteaza in acel oras), se cere sa se determine traseul care are costul minim, plecand dintr-un oras dat start si ajungand intr-un oras dat finis.
Input:
n – numarul de noduri(orase) n – numarul de noduri(orase)
m – numarul de drumuri m – numarul de drumuri
start – nodul(orasul) start start – nodul(orasul) start
finis – nodul(orasul) finish finis – nodul(orasul) finish
v1,w1,c1 v1,w1,c1
v2,w2,c2 v2,w2,c2
…….. ……..
vm,wm,cm => vi,wi,ci semnifica faptul ca exista drum(muchie) intre vi si wi, si costa ci. vm,wm,cm => vi,wi,ci semnifica faptul ca exista drum(muchie) intre vi si wi, si costa ci.
b1,k1 b1,k1
b2,k2 b2,k2
….. …..
bn,kn => bi,ki semnifica faptul ca in orasul(nodul) i, bariera este pozitionata catre bi(dintre nodurile vecine cu i) si mutarea barierei catre alt nod costa ki. bn,kn => bi,ki semnifica faptul ca in orasul(nodul) i, bariera este pozitionata catre bi(dintre nodurile vecine cu i) si mutarea barierei catre alt nod costa ki.
Output:
x1,x2…xp => nodurile ce formeaza traseul de la x1=start la xp=finis, cu xi x(i+1) vecini de la x1 la xp x1,x2…xp => nodurile ce formeaza traseul de la x1=start la xp=finis, cu xi x(i+1) vecini de la x1 la xp
m1,m2,…mp => mi este noul nod catre care se indreapta barieradin nodul xi, respectiv 0, daca bariera nu se muta. m1,m2,…mp => mi este noul nod catre care se indreapta barieradin nodul xi, respectiv 0, daca bariera nu se muta.
Exemplu:
Input: Input:
5 6 5 6
1 3 1 3
1 2 4 1 2 4
1 5 5 1 5 5
2 3 6 2 3 6
5 3 3 5 3 3
3 4 7 3 4 7
2 4 1 2 4 1
2 1 2 1
3 1 3 1
4 2 4 2
2 5 2 5
1 2 1 2
Output: Output:
1 2 3 1 2 3
5 4 0 5 4 0

Observatie:
Daca problema nu are solutie, in Output se va scrie 0.

    1. (1,5p) Având un vector cu numere intregi sortate in ordine crescatoare, creati un arbore binar de cautare, balansat, bazat pe acest vector.
      struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      };
      TreeNode* sortedArrayToBST(int nums[]) {
      };
    2. (1,5p) Având doi arbori binari, implementati un algoritm pentru fuzionarea lor într-un nou arbore binar. Regula de fuzionare este că dacă două noduri se suprapun, atunci suma valorilor nodurilor se utilizeaza ca noua valoare a nodului fuzionat, în caz contrar, nodul care nu este NULL va fi folosit pentru fuzionare.  Arborele va fi reprezentat in C++ cu ajutorul urmatoarei structuri:

      struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      };

      Input: 
      	Arbore 1                 Arbore 2                  
                1                         2                             
               / \                       / \                            
              3   2                     1   3                        
             /                           \   \                      
            5                             4   7                  
      Output: 
      Arborele rezultat din fuzionare:
      	     3
      	    / \
      	   4   5
      	  / \   \ 
      	 5   4   7
      Arborii se vor citi din fisier in urmatorul format (parcurgere in latime, bfs):
      Arbore1: 1 3 2 5
      Arbore2: 2 1 3 # 4 # 7
      Iar rezultatul se va afisa la ecran in urmatorul format:
      3 4 5 5 4 # 7
    3. (1,00p) Având un arbore binar, calculati inaltimea acestuia. Inaltimea este numarul de noduri din cel mai lung drum de la nodul root pana la un nod frunza.
      struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      };
      int maxDepth(TreeNode* root) {}
    4. (1,00p) Având un arbore binar, calculati inaltimea minima a acestuia. Inaltimea minima este numarul de noduri din cel mai scurt drum de la nodul root pana la un nod frunza.
      struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      };
      int minDepth(TreeNode* root) {}
    5. (1,00p) Având un arbore binar, si o valoare sum, determinati daca exista un drum de la nodul root pana la orice nod frunza, astfel incat suma valorilor nodurilor sa fie egala cu sum.
      struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      };
      bool hasPathSum(TreeNode* root, int sum) {}

      Fiind dat urmatorul arbore binar, si sum = 22,
                    5
                   / \
                  4   8
                 /   / \
                11  13  4
               /  \      \
              7    2      1
      returnati true, deoarece exista un drum de la root la o frunza 5->4->11->2 care are suma = 22.
    6. (1,50p) Implementati un program care inverseaza un arbore binar.
      Exemplu:
      Din
     4
   /   \
  2     7
 / \   / \
1   3 6   9

in

     4
   /   \
  7     2
 / \   / \
9   6 3   1


TreeNode* invertTree(TreeNode* root) {

}

17. (1,50p) Avand un arbore binar, returnati media nodurilor de pe fiecare nivel, sub forma de vector.

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]

Explicatie:
Media nodurilor de pe nivelul 0 este 3, pe nivelul 1 este 14.5, si pe nivelul 2 este 11. Deci returnam [3, 14.5, 11].

double[] averageOfLevels(TreeNode* root) {
}

  1. (1,50p) Construiti reprezentarea String al unui arbore binar.
    Exemplul 1:
    Input:
           1
         /   \
        2     3
       /    
      4     
    
    Output: "1(2(4))(3)"
    

    Explicatie: Initial, raspunsul ar trebui sa fie „1(2(4)())(3()())”, dar trebuie sa evitati toate perechile de paranteze care nu sunt necesare(perechi de paranteze goale).
    Raspunsul devine „1(2(4))(3)”.

    Exemplul 2:
    Input:
           1
         /   \
        2     3
         \  
          4 
    
    Output: "1(2()(4))(3)"
    


    char* tree2str(TreeNode* t) {
    }