Leetcode 589. N-ary Tree Preorder Traversal

###### tags: `Tree & Binary Tree` <h1> Leetcode 589. N-ary Tree Preorder Traversal </h1> <ol> <li>問題描述</li> 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) Example 1: Input: root = [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4] Example 2: Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null, null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10] <li>Input的限制</li> <ul> <li>The number of nodes in the tree is in the range [0, 10^4].</li> <li>0 <= Node.val <= 10^4</li> <li>The height of the n-ary tree is less than or equal to 1000.</li> </ul> <li>思考流程</li> <ul> <li>Iterations</li> Preorder的順序是要先走 root, left child，然後 right child。我們利用 stack 來完成整個過程。整個過程會先探索 root，然後把 children 由右至左加入到 stack 中。這樣 left child 才會優先從 stack 中被 pop 出來，達成 preorder 的順序。然後依序從 stack 中 pop node 出來，並拜訪這個 node。 Tree 裡面的所有 nodes 都必須走一遍，所以 time complexity 是 O(n)。在 space complexity 方面，最差的情況為 root 的下方，也就是第二層為剩餘的所有 nodes，這樣 stack 最長就會放滿整個 tree 的 nodes，故為 O(n)。 Time Complexity: O(n); Space Complexity: O(n) <li>Recursion</li> 我們利用 DFS 遍歷整個 tree，當走到的 node 是 None 的時候就結束往下探索，當 node 有值的時候就把值加入到 list 中，並由左向右利用 DFS 遞迴探索 child nodes。 Time complexity 的部分因為需遍歷整個 tree，所以是 O(n); Space complexity 的部分，最差會是一個 height 為 n nodes 的 tree，這樣會造成 stack 的深度為 n 個 nodes，故 space complexity 為 O(n)。 Time Complexity: O(n); Space Complexity: O(n) </ul> <li>測試</li> <ul> <li>test 1</li> Input: root = [1, null, 2, 3, null, 4, 5, null, 6, 7] Output: [1,2,4,5,3,6,7] <li>test 2( edge case )</li> Input: root = None Output: [] 因為 empty list 不是 Node 物件，一旦被放入到 stack 中，讀出來進行操作時會發生錯誤。故如果 root 指向空字串，需要另外處理。 <li>test 3</li> Input: root = [1, null, 2, null, 3, null, 4, null, 5, null, 6] Output: [1, 2, 3, 4, 5, 6]。 <li>test 4</li> Input: root = [1, null, 2, 3, 4, 5, 6] Output: [1, 2, 3, 4, 5, 6]。 </ol>