何为中序遍历

中序是相对于根节点来说的，当遍历一棵二叉树时，先遍历根节点的左子树，中间遍历根节点，最后遍历根节点的右子树。以此类推，遍历子树时也是中序遍历。

二叉树的定义

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

递归实现

二叉树无论前序、中序还是后序遍历，利用递归都是很容易实现的。代码如下：

public List<Integer> inorderTraversal_recursion(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();
    if (root.left != null) {
        res.addAll(inorderTraversal_recursion(root.left));
    }
    res.add(root.val);
    if (root.right != null) {
        res.addAll(inorderTraversal_recursion(root.right));
    }

    return res;
}

非递归实现

一开始自己想的

public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    HashSet<TreeNode> hasFound = new HashSet<>();   //存入已遍历过的节点
    hasFound.add(root);

    while (stack.size() != 0) {
        TreeNode pop = stack.getFirst();    //栈顶元素
        //若栈顶元素的左孩子不为空，且没遍历过，将其入栈
        if (pop.left != null && !hasFound.contains(pop.left)) {
            stack.push(pop.left);
            hasFound.add(pop.left);
        } else {
            res.add(stack.pop().val);   //取出栈顶元素
            //当左孩子为空时，若栈顶元素的右孩子不为空，且没遍历过，将其入栈
            if (pop.right != null && !hasFound.contains(pop.right)) {
                stack.push(pop.right);
                hasFound.add(pop.right);
            }
        }
    }

    return res;
}

优化后的

这个优化版本参考了LeetCode的官方题解。优化后的版本和我开始写的版本最大的区别就是不需要另外用一个HashSet来存储遍历过的节点，实现如下：

public List<Integer> inorderTraversal_stack(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;   //存储当前遍历到的节点
    while (curr != null || !stack.isEmpty()) {
        //若当前节点不为空，将当前节点及其下面的左孩子都入栈
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        //此时curr为空，栈顶节点出栈
        curr = stack.pop();
        res.add(curr.val);
        //开始遍历栈顶节点的右孩子
        curr = curr.right;
    }

    return res;
}