前言

在讲二叉树的遍历之前，我们首先讲一下递归这个东西，很多人，写递归函数靠运气，或者说不只是写递归函数，写任何代码都靠运气，听天由命，有时候自己都不知道自己写的是什么就过了，这样写代码肯定是不行的。

之所以我们会有这种情况是因为，我们在写一个代码的时候没有一个明确的方法体，我们在这里以递归为例子。

递归

我们在写递归算法的时候主要有三要素，每次写递归按照这三要素写，一般不会出错。

1.确定递归函数的参数和返回值： 确认哪些参数是递归过程中需要处理的，那么就在递归函数里加上这个参数，返回值每次递归的返回值一样，返回值很好确定，根据题意来决定。

2.确定终止条件： 我们在写递归函数时经常遇到的错误就是栈溢出，这说明你没有终止条件或者终止条件错误，操作系统也是用栈结构来保存第一次递归的信息。

3.确认单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归过程。

前序遍历

我们刚刚说道递归三要素，接下来我们就拿前序遍历实践一下。

在这之前我们先说明一下，什么是前序遍历

二叉树前序遍历的顺序是根左右，那么上图这棵树的遍历顺序就是ABDECFG

144. 二叉树的前序遍历（点击立即答题）

给你二叉树的根节点 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]

思路就是递归

java代码：

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        //进入递归函数
        preorder(root , list);
        return list;
    }
	//构建递归函数，确认参数和返回值
    public void preorder(TreeNode root , List<Integer> result) {
    	//确定终止条件
        if (root == null) return;
		
		//将结果加入线性表list中
        result.add(root.val);
        //左节点
        preorder(root.left , result);
        //右节点
        preorder(root.right , result);
    }
}

至于单层逻辑就是整个递归函数了，你有了前两个条件才会有第三个条件。

或许还有同学不明白递归，我在这里解释一下,注意看注释；

	public void preorder(TreeNode root , List<Integer> result) {// 这里传过来两个参数的地址
	//如果传入的节点是null，则直接返回上一层
	//比如我们现在进入的的是第三层，那么我们就是返回第二层，并且第二层你是从哪进入第三层，你就返回到哪
    if (root == null) return;

    result.add(root.val);
 	 //再次传入两个参数的地址
 	 //假设我们从这里进入又一个递归函数
    preorder(root.left , result);
 
    preorder(root.right , result);
}

preorder(root.left , result);我们进入这个递归函数

	public void preorder(TreeNode root , List<Integer> result) {// 这里传过来的是root.left和result的地址
	
	//如果root.left == null ，那么直接就返回到preorder(root.left , result);的下一个代码,就是 preorder(root.right , result);之后就会执行preorder(root.right , result);

    if (root == null) return;

    result.add(root.val);
    preorder(root.left , result);
    preorder(root.right , result);
}

对于二叉树的遍历，我们还可以使用迭代法来遍历；

思路

迭代法其实就是将栈模拟出来，而递归是隐藏起来的。

在这里唯一需要注意的一点就是，前序遍历的顺序是根左右，我们在往栈中放的时候先放右节点，再放左节点，这是因为栈是先进后出的。
注：图片来源微信公众号代码随想录

java代码：（请看注释）

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>(); 
        //若根节点为空，直接返回
        if (root == null) return result;
		
		//构建一个栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        //当栈不为空的情况下执行
        while (!stack.isEmpty()) {
        	//将栈顶元素赋予弄得
           TreeNode node = stack.peek();
           //弹出栈顶元素
           stack.pop();
           //因为我们不确定当前节点的子节点是否为空，所以在这里要进行判断
           if (node != null) result.add(node.val);
           else continue;
			
			//将当前节点的右节点放入栈
           stack.push(node.right);
           //将当前节点的左节点放入栈
           stack.push(node.left);
        }
       

        return result;
   
    }
}

若有误，请指教！