校园网设计毕业论文_9 12米农村自建房设计图_电脑培训班有哪些科目_怎样弄一个自己的平台

跟着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;}