1.问题

给你二叉树的根节点 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

2.解题思路

2.1 递归

中序遍历的规则是 根-左-右，然后访问左子树、右子树时同样按照此规则遍历，非常容易通过递归实现，按照规则，代码非常容易写出来。定义 preorderTraversal(root) 为递归遍历函数方法，root 为根节点。伪代码：

root.val;
preorderTraversal(root.left);
preorderTraversal(root.right);

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡n)，最坏情况下树呈现链状，为 O(n)。

2.2 迭代

显示利用栈结构，遍历二叉树。
引用LeetCode动态图解迭代过程：
1）访问根节点

2）根节点入栈

3）左子树根节点遍历、入栈

4）左子树根节点出栈，遍历其左右子节点

5）左根节点左子树不存在，遍历其右子树4

6）左子树遍历完毕，遍历根节点右子树

7）遍历右子树根节点，根节点出栈

8）右子树根节点入栈

9）右子树左节点遍历，入栈

10）右子树左节点遍历完毕，该节点出栈

11）遍历右子树右节点，右子树根节点出栈

12）右子树右节点遍历，入栈

13）右子树遍历完毕，出栈

14）遍历完毕

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

• 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log⁡n)，最坏情况下树呈现链状，为 O(n)。

3.代码

public class Solution {/* 递归* @param root TreeNode类* @return int整型一维数组*/public int[] preorderTraversal (TreeNode root) {// write code hereif (null == root) {return new int[0];}List<Integer> list = new ArrayList();preorderTraversal2(list, root);return list.stream().mapToInt(Integer::valueOf).toArray();}//递归方法public void preorderTraversal2 (List<Integer> list, TreeNode root) {if (null == root) {return;}list.add(root.val);preorderTraversal2(list, root.left);preorderTraversal2(list, root.right);}//迭代，栈思想public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (null == root) {return res;}Stack<TreeNode> stack = new Stack<>();stack.add(root);TreeNode p;while (!stack.isEmpty()) {p = stack.pop();res.add(p.val);//先把右节点入栈if (null != p.right) {stack.add(p.right);}if (null != p.left) {stack.add(p.left);}}return res;}
}