跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录
LeetCode：144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
前序遍历递归法
- 确定入参，返回值
- 确定终止条件
- 确定单层递归逻辑
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();treversal(root, res);return res;}private void treversal(TreeNode root, List<Integer> res){if(root == null){return;}res.add(root.val);treversal(root.left, res);treversal(root.right, res);}
前序遍历迭代法（非递归法）
通过栈来实现非递归遍历，因为是放入栈，所以需要先放right然后再放left，，先进后出；注意判空
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();if(node != null){res.add(node.val);}else{continue;}stack.push(node.right);stack.push(node.left);}return res;}
也可以这样，只是判空逻辑不同
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}return result;}
