力扣 LeetCode 144. 二叉树的前序遍历（Day6：二叉树）

解题思路：

方法一：递归（中左右）

class Solution {List<Integer> res = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {recur(root);return res;}public void recur(TreeNode root) {if (root == null) return;res.add(root.val);recur(root.left);recur(root.right);}
}

方法二：迭代（非递归法）

也就是用栈

重点弄懂前序是怎么用栈来实现的（以前序为基准，推出后序和中序）

因为栈是先进后出，所以实现前序，是中右左，先放右节点，再放左节点

后序迭代的推导：

正常情况下，前序是中左右（迭代法时栈用中右左），后序是左右中，那么：

中左右->中右左->左右中

先交换语句，再整体调用Collections.reverse()，就可以得到后序的迭代法

本题为前序迭代：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {Deque<TreeNode> stack = new ArrayDeque<>();List<Integer> res = new ArrayList<>();if (root == null) return res;stack.push(root);while (!stack.isEmpty()) {//前面判断过了，所以此时 node 必不为空TreeNode node = stack.pop();res.add(node.val);if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}return res;}
}