LeetCode 75 Level 1 - Day 6 Tree

589. N-ary Tree Preorder Traversal

• 題目連結
• 難易度：Easy

題目敘述

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

預設函數

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorder(struct Node* root, int* returnSize) {

}

題目限制

• The number of nodes in the tree is in the .
• 
• The height of the n-ary tree is less than or equal to 1000.

解題過程及程式碼

今天又進入了一個新主題: Tree，題目給一個多元樹(n-ary tree)，要回傳這個樹的Preorder Traversal(前序走訪)，下圖是題目所給Example 1，我們首先由①出發，若有子階就跳到第一個子階③(若沒有則結束)，③若有子階就跳到第一個子階⑤(若沒有則跳到同一層的其他節點)，⑤沒有子階就跳到⑥，⑥也沒有子階而且③⑤⑥都走完了就跳到③同層的②，②也沒子階就跳到同層的④，所以最後的順序就是要回傳①③⑤⑥②④。

我們先從多元樹簡化到二元樹來複習一下前序走訪（Preorder Traversal），重點在每次程式都優先處理自己再到左子階再到右子階。

• A. 二元樹中的前序走訪（Preorder Traversal）程式碼

  void print_preorder(node *ptr) {
      if (ptr != NULL) {
          printf("[%2d]\n", ptr->data);  // 先印自己
          print_preorder(ptr->left);  // 再印左子節點
          print_preorder(ptr->right);  // 最後印右子節點
      }
  }
  

• B. 可參考資料 (查詢 Tree Traversal)
  1. Binary Tree: Traversal(尋訪)
  2. Tree Traversal in C

接下來我們就可以利用二元樹的走訪來實現題目要的多元樹的走訪

• A. 利用題目所提供的節點中的元素numChildren避免訪問到錯誤的位置

  void run_preorder3(struct Node* ptr) {
      int num = ptr->numChildren;
      int i;
  
      if (num >= 0) {
          append_array(ptr->val);
          for (i=0; i<num; i++) {  // 避免ptr->children[i]超過範圍
              run_preorder3(ptr->children[i]);
          }
      }
  }
  

• B. 要利用numChildren判斷是否節點還有子階

  void run_preorder4(struct Node* ptr) {
      int num = ptr->numChildren;
      int i;
      if (ptr != NULL) {
          append_array(ptr->val);
          if (num > 0) {  // 等於0就不用再向下訪問了
              for (i=0; i<num; i++) {
                  run_preorder3(ptr->children[i]);
              }
          }
      }
  }
  

• 最後利用前序走訪列出所有的元素 (程式碼上傳)

  int* dynArr;
  int dynArr_index;
  
  int* preorder(struct Node* root, int* returnSize) {
      dynArr = (int *)malloc(10000 * sizeof(int));
      if (root == NULL) {
          *returnSize = 0;
          return NULL;
      }
  
      dynArr_index = 0;
      run_preorder4(root);
  
      *returnSize = dynArr_index;
      return dynArr;
  }
  
  void run_preorder4(struct Node* ptr) {
      int num = ptr->numChildren;
      int i;
      if (ptr != NULL) {
          append_array(ptr->val);    // 先處理自己
          if (num > 0) {             // 再依序處理自己的子階
              for (i=0; i<num; i++) {
                  run_preorder3(ptr->children[i]);
              }
          }
      }
  }
  
  void append_array(int val) {
      dynArr[dynArr_index] = val;
      dynArr_index += 1;
  }
  

今天就到這邊，謝謝大家!