144.二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例1：
1
\
2
/
3
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
题目来源：力扣（LeetCode）
迭代思路
能否写出：不能写出，需要参考思路
时间：60分钟
思路：这次使用的是迭代算法
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode pop = stack.pop(); result.add(pop.val); if (pop.right != null) { stack.push(pop.right); } if (pop.left != null) { stack.push(pop.left); } } return result; } }
时间复杂度：O(n)
遍历每个节点的次数，对于先序遍历而言，每个节点都需要被访问一次，因此遍历的次数是 O(n)，其中 n 是节点的总数。
空间复杂度：O(n)
迭代算法的空间复杂度为 O(max(h, n))，其中 h 是二叉树的高度，n 是节点的总数。在最坏情况下，即二叉树为链式结构时，空间复杂度为 O(n)。
其他思路：
递归：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); preorder(root, result); return result; } private void preorder(TreeNode node, List<Integer> result) { if (node == null) { return; } result.add(node.val); // 访问当前节点 preorder(node.left, result); // 递归遍历左子树 preorder(node.right, result); // 递归遍历右子树 } }
时间复杂度：O(n)
空间复杂度：O(n)
Morris 遍历： 看不懂 啊~~(╯°Д°)╯︵ ┻━┻
有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
新建临时节点，令该节点为 root；
如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
重复步骤 2 和步骤 3，直到遍历结束。
这样我们利用 Morris 遍历的方法，前序遍历该二叉树，即可实现线性时间与常数空间的遍历。
