144.Binary Tree Preorder Traversal === ###### tags: `Easy`,`Tree`,`DFS`,`Stack`,`Binary Tree` [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) ### 題目描述 Given the `root` of a binary tree, return *the preorder traversal of its nodes' values*. ### 範例 **Example 1:** ![](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg) ``` Input: root = [1,null,2,3] Output: [1,2,3] ``` **Example 2:** ``` Input: root = [] Output: [] ``` **Example 3:** ``` Input: root = [1] Output: [1] ``` **Constraints**: * The number of nodes in the tree is in the range `[0, 100]`. * -100 <= `Node.val` <= 100 **Follow up**: Recursive solution is trivial, could you do it iteratively? ### 解答 #### Javascript recursive ```javascript= function preorderTraversal(root) { const result = []; if (root === null) return result; result.push(root.val); result.push(...preorderTraversal(root.left)); result.push(...preorderTraversal(root.right)); return result; } ``` iterative ```javascript= function preorderTraversal2(root) { const result = []; if (root === null) return result; const stack = [root]; while (stack.length > 0) { const node = stack.pop(); result.push(node.val); if (node.right !== null) stack.push(node.right); if (node.left !== null) stack.push(node.left); } return result; } ``` > [name=Marsgoat] [time= Jan 9, 2023] #### Python ```python= class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return root traversal, stk = [], [root] while stk: node = stk.pop() traversal.append(node.val) if node.right: stk.append(node.right) if node.left: stk.append(node.left) return traversal ``` > [name=Ron Chen] [time= Jan 9, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)