94. 二叉树的中序遍历

查看题目

简单

树

二叉树

递归

中频

解法一：迭代法

时间复杂度：O(n) | 空间复杂度：O(n) | 推荐使用

动画演示

二叉树结构:

准备就绪 - 输入二叉树结构（用逗号分隔，null表示空节点），然后点击开始

中序遍历结果:

代码实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

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;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

使用栈实现二叉树的中序遍历，按照左-根-右的顺序访问节点。

解法二：递归法

时间复杂度：O(n) | 空间复杂度：O(h)

动画演示

二叉树结构:

准备就绪 - 输入二叉树结构（用逗号分隔，null表示空节点），然后点击开始

中序遍历结果:

代码实现

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

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

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;
    }
}

时间复杂度：O(n)

空间复杂度：O(h)

递归实现二叉树的中序遍历，按照左-根-右的顺序访问节点。