一. 题目

二. 思路

• 中序遍历：左根右顺序。

三. 代码

1. 递归

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

    TreeNode()
    {
    }

    TreeNode(int val)
    {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

    void dfs(TreeNode cur)
    {
        if (cur == null) return;
        if (cur.left != null) dfs(cur.left);
        ans.add(cur.val);
        if (cur.right != null) dfs(cur.right);
    }

    public List<Integer> inorderTraversal(TreeNode root)
    {
        ans.clear();
        dfs(root);
        return ans;
    }
}

2. 迭代

class Solution
{
    final List<Integer> ans = new ArrayList<>();
    final Deque<TreeNode> stk = new ArrayDeque<>(110);//栈

    public List<Integer> inorderTraversal(TreeNode root)
    {
        stk.clear();
        ans.clear();

        while (root != null || !stk.isEmpty())
        {
            while (root != null)//先遍历左儿子，直到没有左儿子
            {
                stk.offerLast(root);
                root = root.left;
            }

            root = stk.pollLast();//再遍历根
            ans.add(root.val);
            root = root.right;//再遍历右儿子
        }

        return ans;
    }
}