Следующая Заполнение справа Указатели в каждом узле двоичного дерева

Я пытаюсь сделать this problem on Leetcode в С.Следующая Заполнение справа Указатели в каждом узле двоичного дерева

Учитывая следующее бинарное дерево,

После вызова вашей функции, дерево должно выглядеть :

 1 -> NULL 
/\ 
    2 -> 3 -> NULL 
/\ \ 
4-> 5 -> 7 -> NULL

Что я делаю создаю очереди на уровень порядка обход дерева и присоединение следующего указателя каждого узла к следующему Qu eue на каждом уровне . Чтобы разделить уровни, я нахожу указатель NULL.

Итак, для примера выше: очередь -> [1, #, 2,3, #, 4,5,7, #], где # - NULL ptr.

Вот мой код проблемы ::

/** 
* Definition for binary tree with next pointer. 
* struct TreeLinkNode { 
* int val; 
* struct TreeLinkNode *left, *right, *next; 
* }; 
* 
*/ 
bool isEmpty(int start,int end){ 
    if(start > end) 
     return true; 
    return false; 
} 

void connect(struct TreeLinkNode *root) { 
    if(!root || (!root->left && !root->right)) 
     return; 
    int cap = 1000; 
    struct TreeLinkNode** q = malloc(cap* sizeof(struct TreeLinkNode*)); 
    int start=0, end=-1, curLevel=1, nextLevel=0; 
    // enqueue 
    q[++end] = root; 
    while(isEmpty(start, end) == false){ 
     //dequeue 
     struct TreeLinkNode* temp = q[start++]; 
     curLevel--; 
     if(isEmpty(start, end) == false && curLevel !=0) 
      temp->next = q[start]; 
     if(temp->left){ 
      q[++end] = temp->left; 
      nextLevel++; 
     } 
     if(temp->right){ 
      q[++end] = temp->right; 
      nextLevel++; 
     } 
     if(curLevel ==0){ 
      curLevel = nextLevel; 
      nextLevel =0; 
     } 
     if(start> cap-50 || end> cap-50) 
      q = realloc(q, 2*cap*sizeof(struct TreeLinkNode *)); 
    } 
    free(q); 
}

код, по-видимому работает для небольших тестовых случаев, но и для более крупных на Leetcode код дает ошибку во время выполнения. Я не знаю, что я делаю неправильно. Пожалуйста, помогите. Я был бы очень признателен, если бы кто-то мог запустить этот код на Leetcode

источник

2016-01-13 sajal garg

В соответствии с тем, что вы написали, кажется, что вы слишком часто ставите указатель NULL: он должен быть после каждого уровня, но в вашем коде он находится после каждого анализируемого узла. –

Вы правы. Для решения этой проблемы я сделал несколько изменений. Но код еще не работает. –

И да спасибо за указание на ошибку –

Конец уровня возникает, когда вы анализируете последний узел предыдущего уровня. Поскольку каждый уровень заканчивается значением NULL в q, когда temp равно NULL, это означает, что полный уровень был проанализирован, и вы можете завершить следующий уровень, вставив NULL.

Так что я сделал небольшие изменения в код:

void connect(struct TreeLinkNode *root) { 
    int cap = 1000; 
    struct TreeLinkNode** q = malloc(cap* sizeof(struct TreeLinkNode*)); 
    int start=0, end=-1; 
    // enqueue 
    q[++end] = root; 
    q[++end] = NULL; // End of first level 
    for (;;) { 
     //dequeue 
     struct TreeLinkNode* temp = q[start++]; 
     if (temp == NULL) { 
      if (q[start] == NULL) // Two consecutives NULL means end of tree 
       break; 
      q[++end] = NULL; // End of level 
     } else { 
      temp->next = q[start]; 
      if(temp->left) 
       q[++end] = temp->left; 
      if(temp->right) 
       q[++end] = temp->right; 
      if (end > cap-50) { // end is always greater or equal to start 
       q = realloc(q, 2*cap*sizeof(struct TreeLinkNode *)); 
      } 
     } 
    } 
    free(q); 
}

Я не могу проверить его в режиме реального времени прямо сейчас, поэтому он не может работать напрямую, это в основном за идею.

источник

2016-01-14 06:29:57

Следующая Заполнение справа Указатели в каждом узле двоичного дерева

ответ

Смежные вопросы