Các câu hỏi phỏng vấn [42]

3 Comments

1. Chấn Ngô
   Posted 08/05/2012 at 9:32 am | Permalink

   Hello a NQH,

   Em nghĩ bài này mình dùng cách duyệt cây theo giải thuật Moris Traversal, trong quá trình duyệt mình sẽ thay đổi tree, duyệt xong sẽ chuyển ngược về tree ban đầu. Ý tưởng chính là như sau:
   1. Initialize current as root
   2. While current is not NULL
   If current does not have left child
   a) Print current’s data
   b) Go to the right, i.e., current = current->right
   Else
   a) Make current as right child of the rightmost node in current’s left subtree
   b) Go to this left child, i.e., current = current->left
   Theo cách này thì ko yêu cầu thêm về bộ nhớ là hằng số (constant space).
   Em copy đoạn C++ code người # viết mọi người kiểm tra xem:

   #include
   #include
    
   /* A binary tree tNode has data, pointer to left child
      and a pointer to right child */
   struct tNode
   {
      int data;
      struct tNode* left;
      struct tNode* right;
   };
    
   /* Function to traverse binary tree without recursion and
      without stack */
   void MorrisTraversal(struct tNode *root)
   {
     struct tNode *current,*pre;
    
     if(root == NULL)
        return; 
    
     current = root;
     while(current != NULL)
     {
       if(current->left == NULL)
       {
         printf(" %d ", current->data);
         current = current->right;
       }
       else
       {
         /* Find the inorder predecessor of current */
         pre = current->left;
         while(pre->right != NULL && pre->right != current)
           pre = pre->right;
    
         /* Make current as right child of its inorder predecessor */
         if(pre->right == NULL)
         {
           pre->right = current;
           current = current->left;
         }
    
         /* Revert the changes made in if part to restore the original
           tree i.e., fix the right child of predecssor */
         else
         {
           pre->right = NULL;
           printf(" %d ",current->data);
           current = current->right;
         } /* End of if condition pre->right == NULL */
       } /* End of if condition current->left == NULL*/
     } /* End of while */
   }
    
   /* UTILITY FUNCTIONS */
   /* Helper function that allocates a new tNode with the
      given data and NULL left and right pointers. */
   struct tNode* newtNode(int data)
   {
     struct tNode* tNode = (struct tNode*)
                          malloc(sizeof(struct tNode));
     tNode->data = data;
     tNode->left = NULL;
     tNode->right = NULL;
    
     return(tNode);
   }
    
   /* Driver program to test above functions*/
   int main()
   {
    
     /* Constructed binary tree is
               1
             /   \
           2      3
         /  \
       4     5
     */
     struct tNode *root = newtNode(1);
     root->left        = newtNode(2);
     root->right       = newtNode(3);
     root->left->left  = newtNode(4);
     root->left->right = newtNode(5); 
    
     MorrisTraversal(root);
    
     getchar();
     return 0;
   }
   
   Reply
   • numos
     Posted 08/11/2012 at 5:52 am | Permalink

     Dear bạn Chấn Ngô,

     Mình thử check lời giải của bạn. Bạn in ra kết quả theo thứ tự trước Preorder trong khi yêu cầu bài toán là Inorder.
     Bản kiểm tra lại xem.

     Ý tưởng của mình để in theo thứ tự Inorder dùng O(1)-memory.

     1. Initialize current as root
     2. While current is not NULL
     2.1. Print current’s data.
     2.2. If current->left is NULL then current = current->right.
     Else
     {
     2.2.1. Make the right child of the rightmost node in current->left is current->right.
     2.2.2. current = current->left.
     }

     #include
     #include
     /* A binary tree tNode has data, pointer to left child
     and a pointer to right child */
     struct tNode
     {
     int data;
     struct tNode* left;
     struct tNode* right;
     };

     void Inorder(struct tNode *root)
     {
     struct tNode *current,*node;

     current = root;
     while(current != NULL)
     {
     printf(” %d “, current->data);
     if(current->left == NULL)
     {
     current = current->right;
     }
     else
     {
     /* Find the rightmost node of current->left */
     node = current->left;
     while(node->right != NULL)
     node = node->right;
     /* Set the right child of the rightmost node of current->left is current->right*/
     node->right = current->right;

     current = current->left;
     }
     } /* End of while */
     }

     /* UTILITY FUNCTIONS */
     /* Helper function that allocates a new tNode with the
     given data and NULL left and right pointers. */
     struct tNode* newtNode(int data)
     {
     struct tNode* tNode = (struct tNode*)
     malloc(sizeof(struct tNode));
     tNode->data = data;
     tNode->left = NULL;
     tNode->right = NULL;

     return(tNode);
     }

     /* Driver program to test above functions*/
     int main()
     {

     /* Constructed binary tree is
     1
     / \
     2 3
     / \
     4 5
     */
     struct tNode *root = newtNode(1);
     root->left = newtNode(2);
     root->right = newtNode(3);
     root->left->left = newtNode(4);
     root->left->right = newtNode(5);

     Inorder(root);

     getchar();
     return 0;
     }
     Reply
2. Xuân Lương
   Posted 20/08/2012 at 3:11 pm | Permalink

   Hi GS. Hưng
   Bài 111 em nghĩ có thể giải dựa trên ý tưởng sau:
   - Về cơ bản thì ta dùng một con trỏ đi tuần tự ở nút gốc rồi rẽ sang trái cho tới khi chạm nút lá thì print data -> đi ngược lên nút cha -> print data -> rẽ phải …
   - Để giải quyết yêu càu không gian là O(1) thì ta có một con trỏ để duyện trong cây và một biến đi kèm để biết là con trỏ đó đã rẽ phải / trái mấy lần. Biến đó được cập nhật dựa trên cơ chế là:
   – Nếu con trỏ ở root thì foo = 1
   – Một lần rẽ trái thì foo = foo * 2
   – Một lần rẽ phải thì foo = foo * 2 + 1
   Với cách này, khi con trỏ chạy tới nút lá, ta gán nó trở về nút gốc và duyệt lại cho tới nút cha của nút cuối cùng mà nó đã trỏ tới. Việc này time-consuming nhưng có thể thỏa mãn yêu cầu về bộ nhớ?
   Reply