給你二叉樹的根節點?root?，返回它節點值的?前序?遍歷。

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,2,3]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

示例 4：

輸入：root = [1,2]
輸出：[1,2]

示例 5：

輸入：root = [1,null,2]
輸出：[1,2]

提示：

• 樹中節點數目在范圍?[0, 100]?內
• -100 <= Node.val <= 100

解法：

本人解法

使用遞歸的方法求解

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}hasNextNode(root, list);return list;}public void hasNextNode(TreeNode root, List<Integer> list) {list.add(root.val);if (root.left != null) {hasNextNode(root.left, list);}if (root.right != null) {hasNextNode(root.right, list);}}
}

官方解法：

方法一與本人解法相同

方法二：迭代
思路與算法

我們也可以用迭代的方式實現方法一的遞歸函數，兩種方式是等價的，區別在于遞歸的時候隱式地維護了一個棧，而我們在迭代的時候需要顯式地將這個棧模擬出來，其余的實現與細節都相同，具體可以參考下面的代碼。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {res.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return res;}
}

復雜度分析

時間復雜度：

O(n)，其中 n 是二叉樹的節點數。每一個節點恰好被遍歷一次。

空間復雜度：

O(n)，為迭代過程中顯式棧的開銷，平均情況下為 O(log?n)，最壞情況下樹呈現鏈狀，為 O(n)。

---

注：官方解法部分

作者：力扣官方題解
鏈接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/461821/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。