前言

二叉树的遍历应该属于高频的面试题，在LeetCode里递归遍历属于简单题、非递归遍历属于中等难度题。常见于初中级程序员的面试过程中，多年前笔者也曾被面过这道题，也常出现在阿里巴巴的面试题中。
本文尝试将二叉树的前、中、后序遍历讲清楚，并将代码思路捋一捋。

二叉树遍历

常考的除了二叉树的前中后序遍历（深度遍历）还有二叉树的层序遍历。二叉树对应的遍历方法为：

• 前序遍历：根结点-->左叶子结点-->右叶子结点。
• 中序遍历：左叶子结点-->根结点-->右叶子结点。
• 后序遍历：左叶子结点-->右叶子结点-->根结点。

可以看出，二叉树所谓的前中后是相对于根结点而言的，根结点在最前面即为前序，根结点在中间即为中序，根结点在最后面即为后序。理解了这一层，基本就不难手写出遍历的结果了。我们手写下下面二叉树的遍历结果：

二叉树

• 前序遍历：1->2->4->6->3->5->7
• 中序遍历：4->6->2->1->3->7->5
• 后序遍历：6->4->2->7->5->3->1

二叉树的递归遍历

递归遍历是最简单的实现方法，理解起来也比较简单。先粘贴代码：
定义TreeNode

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

leetcode官方给的遍历答案

class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List < Integer > res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }
}

未完待续