目录

题目要求：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

方法一：递归

方法二：迭代

思路分析：

复杂度分析

代码展示：

方法三：迭代进阶

思路分析：

代码展示：

方法三：Morris 遍历

思路分析：

代码展示：

复杂度分析

---

题目要求：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

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

示例 2：

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

示例 3：

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

方法一：递归

递归的方法在之前的博客中已经写过，需要的小伙伴可以点击链接查看

递归求二叉树的前中后序遍历

这篇文章主要来讲解非递归的方法对二叉树进行前序遍历

方法二：迭代

思路分析：

迭代的方式其实与递归是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码

复杂度分析

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

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

代码展示：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {//创建一个栈和一个数组Deque<TreeNode> stack = new LinkedList<>();List<Integer> list = new ArrayList<>();//节点非空或者栈非空进入循环while(root != null || !stack.isEmpty()){//节点非空进循环while(root != null){//所有根节点入栈stack.push(root);//根结点的值入数组list.add(root.val);root = root.left;}//此时说明栈顶节点的左子树为空，//那么把它弹出并且接下来判断栈顶节点的右子树root = stack.pop().right;}//栈为空出循环，返回数组return list;}
}

方法三：迭代进阶

思路分析：

写完上面的迭代后发现其实还有更简便的代码，因为前序的遍历方式是根左右，那么我们可以先把根入栈进入循环后，在出栈顶元素（根）将值存放在答案数组中，然后先入右子树，再入左子树（这样出栈顺序就是先左后右），直至栈为空，出循环后，这样答案数组中的元素刚好就是前序遍历

代码展示：

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

方法三：Morris 遍历

Morris 遍历使用二叉树节点中大量指向 null 的指针，由 Joseph Morris 于 1979 年发明。

思路分析：

将当前根节点的最右侧节点的right指向当前根节点，省去了栈的维护，连接之后可以直接顺着节点遍历完整个二叉树，以下图为例：

代码展示：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}//创建两个节点，一个指向根节点，//另一个用来寻找当前根节点最右侧的节点TreeNode cur1 = root;TreeNode cur2 = null;while(cur1 != null){cur2 = cur1.left;if(cur2 != null){//此时cur2.right即不能为空，也不能指向当前根节点while(cur2.right != null && cur2.right != cur1){//继续向右寻找cur2 = cur2.right;}//此时出循环有两种可能//1.cur2.right为空if(cur2.right == null){//那么让他指向当前根节点cur2.right = cur1;list.add(cur1.val);//cur1继续向左移动cur1 = cur1.left;continue;}//2.cur2.right已经指向当前根节点//说明当前根节点已经访问过else {//断开连接cur2.right = null;}}else{list.add(cur1.val);}cur1 = cur1.right;}return list;}
}

复杂度分析

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

• 空间复杂度：O(1)，Morris 遍历的优点就在于不需要额外的维护一个栈，省去了O(n)的空间复杂度