力扣144 二叉树的前序遍历 Java版本

---

题目描述

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

示例 1：

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

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
示例 5：

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

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

递归方法

递归的第一步就是找到递归出口，这里是root为null的时候结束递归，因为如果root为null则既没有val也没有子树，所以就不需要继续往下递归了。
接下来就是按照需要遍历的顺序来执行此方法，大部分时候不要深入考虑递归的具体实现，因为越是考虑越是混乱，直接按照顺序交给计算机去执行就可以了。

代码

class Solution {//使用递归的方法来进行前序遍历public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root,result);return  result;}public void preorder(TreeNode root,List<Integer> result){//递归出口if (root==null) {return;}//遍历中间节点result.add(root.val);//遍历左孩子preorder(root.left,result);//遍历右孩子preorder(root.right,result);}
}

非递归方法

思路在代码中详细注释了

代码

class Solution {//使用非递归的方法来完成public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root,result);return  result;}public void preorder(TreeNode root,List<Integer> result){//如果root为空则直接返回if (root==null){return;}//前序遍历需要把当前节点遍历完，再把左子树都遍历完之后，再开始遍历右子树//每个节点都是这样的顺序，所以需要保存记录当前节点的右孩子，因为需要左子树都遍历完才轮到右孩子//考虑使用栈的方法，因为栈可以先把一部分暂时不用的信息保存到栈中Stack<TreeNode> stack = new Stack<>();//先把root入栈stack.push(root);//循环遍历直到所有节点都完成遍历while (!stack.isEmpty()){TreeNode treeNode = stack.pop();result.add(treeNode.val);//将右孩子入栈，再将左孩子入栈，这样出栈之后才是左孩子优先if(treeNode.right!=null){//如果是空的就不需要入栈了stack.push(treeNode.right);}//将左孩子入栈if(treeNode.left!=null){stack.push((treeNode.left));}}}
}