# 94. 二叉树的中序遍历

# 题目描述

给定一个二叉树的根节点 root，返回它的中序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

1
2

示例 2：

输入：root = []
输出：[]

1
2

# 思路

前序、中序、后序到底差在哪里？其实只在处理当前节点的位置。中序遍历是左中右：先递归左子树，再记录当前节点，最后递归右子树。

按照代码随想录的递归三部曲来写：参数是当前节点和存放答案的数组；遇到空节点返回；单层逻辑按左中右执行。录友们可以对照前序的中左右、后序的左右中，看看 push_back 移到哪里了。

# 模拟过程

以 [1,null,2,3] 为例：节点 1 没有左子树，先记录 1；再进入节点 2 的左子树，记录 3；最后回到节点 2，记录 2，得到 [1,3,2]。

下面这张主站遍历顺序图可以帮助录友区分三种递归访问次序：

# 解题代码

class Solution {
    void traversal(TreeNode* cur, vector<int>& result) {
        if (cur == nullptr) return;
        traversal(cur->left, result);     // 左
        result.push_back(cur->val);       // 中：左子树处理完后才记录根节点
        traversal(cur->right, result);    // 右
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 复杂度分析

时间复杂度：O(n)，每个节点访问一次。
空间复杂度：O(h)，递归栈最多占用树高 h；结果数组另占 O(n)。

# 其他语言

# Python3

class Solution:
    def inorderTraversal(self, root):
        result = []
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(root)
        return result

1
2
3
4
5
6
7
8
9
10
11

# Java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    void dfs(TreeNode node, List<Integer> result) {
        if (node == null) return;
        dfs(node.left, result);
        result.add(node.val);
        dfs(node.right, result);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# Go

func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil { return }
        dfs(node.Left)
        result = append(result, node.Val)
        dfs(node.Right)
    }
    dfs(root)
    return result
}

1
2
3
4
5
6
7
8
9
10
11
12

# JS

var inorderTraversal = function(root) {
    const result = [];
    function dfs(node) {
        if (node === null) return;
        dfs(node.left);
        result.push(node.val);
        dfs(node.right);
    }
    dfs(root);
    return result;
};