力扣 LeetCode 94. 二叉树的中序遍历（Day6：二叉树）

解题思路：

方法一：递归（左中右）

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        recur(root);
        return res;
    }

    public void recur(TreeNode root) {
        if (root == null) return;
        recur(root.left);
        res.add(root.val);
        recur(root.right);
    }
}

方法二：迭代（非递归法）

前中后序迭代法都是使用栈

前序和后序使用类似的方法

中序方法不同与前序和后序，需要单独区分

 cur != null 时，首先 cur = cur.left 遍历到底进行栈push

为空时，回到上一个不为空的位置并弹出该值，继续 cur = cur.left 遍历该值右边的位置

注意while循环条件

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }
}