94. 二叉树的中序遍历

题目描述

输入二叉树的根节点 root。二叉树按层序写成数组，空位置用 null 表示，例如 [3,9,20,null,null,15,7]。

按中序遍历这棵树：先遍历左子树，再访问根节点，最后遍历右子树，子树内部也按同样规则。

返回访问到的节点值组成的数组。空树返回空数组。

示例 1

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

解释：根 1 没有左子树，先输出 1；右子树以 2 为根、3 为左孩子，得 3、2。

示例 2

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,2,6,5,7,1,3,9,8]

解释：左子树得 4,2,6,5,7，然后是根 1，再是右子树的 3,9,8。

示例 3

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

解释：空树。

示例 4

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

数据范围

节点数在 [0, 100] 范围内。
-100 <= Node.val <= 100

进阶：递归写法很直接，能否改用迭代实现？

解题思路：迭代（显式栈）

用栈保存尚未访问的祖先，一直向左入栈；弹栈访问，再转向右子树。

为什么正确

完成向左下降后，栈顶是当前左侧路径上下一次应访问的节点；结果始终是完整中序序列的前缀。

复杂度分析

时间 O(n)，额外空间 O(h)，输出空间 O(n)。

易错点

入栈不代表访问；必须在左子树处理完成后弹栈写入结果。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def inorderTraversal(self, root):
        stack, result = [], []
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            result.append(cur.val)
            cur = cur.right
        return result

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

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<TreeNode*> stack; vector<int> result;
        TreeNode* cur = root;
        while (cur || !stack.empty()) {
            while (cur) {
                stack.push_back(cur);
                cur = cur->left;
            }
            cur = stack.back(); stack.pop_back();
            result.push_back(cur->val);
            cur = cur->right;
        }
        return result;
    }
};

func inorderTraversal(root *TreeNode) []int {
    stack, result := []*TreeNode{}, []int{}
    cur := root
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]; stack = stack[:len(stack)-1]
        result = append(result, cur.Val)
        cur = cur.Right
    }
    return result
}

var inorderTraversal = function(root) {
    const stack = [], result = [];
    let cur = root;
    while (cur || stack.length) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        result.push(cur.val);
        cur = cur.right;
    }
    return result;
};

function inorderTraversal(root: TreeNode | null): number[] {
    const stack: TreeNode[] = [], result: number[] = [];
    let cur: TreeNode | null = root;
    while (cur || stack.length) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop()!;
        result.push(cur.val);
        cur = cur.right;
    }
    return result;
};

载入编辑器，自己跑一遍 →

其他解法

递归最简洁但依赖调用栈；显式栈把递归改写成迭代，空间同为 O(h)；Morris 借用空指针当线索，把空间压到 O(1)，但会临时改动树。

解法 2：递归时间 O(n)，空间 O(n)

按照中序遍历的定义直接写：先递归遍历左子树，再记录当前节点的值，最后递归遍历右子树。空节点直接返回。

代码最短，完全对应定义。递归由系统调用栈实现，树退化成链时深度为 n，极端情况下可能栈溢出。

class Solution:
    def inorderTraversal(self, root):
        result = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)

        dfs(root)
        return result

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

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
}

class Solution {
public:
    void dfs(TreeNode* node, vector<int>& result) {
        if (!node) return;
        dfs(node->left, result);
        result.push_back(node->val);
        dfs(node->right, result);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root, result);
        return result;
    }
};

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

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

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const dfs = (node: TreeNode | null): void => {
        if (!node) return;
        dfs(node.left);
        result.push(node.val);
        dfs(node.right);
    };
    dfs(root);
    return result;
}

解法 3：Morris 中序遍历时间 O(n)，空间 O(1)

利用叶子节点的空右指针代替栈。对当前节点 cur：若无左子树，访问它并转向右孩子；否则找到左子树中最右的节点 pre（即 cur 的中序前驱）。如果 pre.right 为空，就让它指向 cur（建立线索），然后去遍历左子树；如果 pre.right 已经指向 cur，说明左子树遍历完了，拆掉线索、访问 cur、转向右孩子。

只用 O(1) 额外空间，每条边最多走两次，总时间仍是 O(n)。代价是遍历过程中会临时修改树结构，并发场景不安全，代码也更难理解。

class Solution:
    def inorderTraversal(self, root):
        result = []
        cur = root
        while cur:
            if not cur.left:
                result.append(cur.val)
                cur = cur.right
                continue
            # 找左子树中最右的节点（中序前驱）
            pre = cur.left
            while pre.right and pre.right is not cur:
                pre = pre.right
            if not pre.right:
                pre.right = cur      # 建立线索，先去遍历左子树
                cur = cur.left
            else:
                pre.right = None     # 左子树已遍历完，拆掉线索
                result.append(cur.val)
                cur = cur.right
        return result

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                result.add(cur.val);
                cur = cur.right;
                continue;
            }
            TreeNode pre = cur.left;
            while (pre.right != null && pre.right != cur) pre = pre.right;
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            } else {
                pre.right = null;
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode* cur = root;
        while (cur) {
            if (!cur->left) {
                result.push_back(cur->val);
                cur = cur->right;
                continue;
            }
            TreeNode* pre = cur->left;
            while (pre->right && pre->right != cur) pre = pre->right;
            if (!pre->right) {
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
};

func inorderTraversal(root *TreeNode) []int {
	result := []int{}
	cur := root
	for cur != nil {
		if cur.Left == nil {
			result = append(result, cur.Val)
			cur = cur.Right
			continue
		}
		pre := cur.Left
		for pre.Right != nil && pre.Right != cur {
			pre = pre.Right
		}
		if pre.Right == nil {
			pre.Right = cur
			cur = cur.Left
		} else {
			pre.Right = nil
			result = append(result, cur.Val)
			cur = cur.Right
		}
	}
	return result
}

var inorderTraversal = function(root) {
    const result = [];
    let cur = root;
    while (cur) {
        if (!cur.left) {
            result.push(cur.val);
            cur = cur.right;
            continue;
        }
        let pre = cur.left;
        while (pre.right && pre.right !== cur) pre = pre.right;
        if (!pre.right) {
            pre.right = cur;
            cur = cur.left;
        } else {
            pre.right = null;
            result.push(cur.val);
            cur = cur.right;
        }
    }
    return result;
};

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    let cur = root;
    while (cur) {
        if (!cur.left) {
            result.push(cur.val);
            cur = cur.right;
            continue;
        }
        let pre: TreeNode = cur.left;
        while (pre.right && pre.right !== cur) pre = pre.right;
        if (!pre.right) {
            pre.right = cur;
            cur = cur.left;
        } else {
            pre.right = null;
            result.push(cur.val);
            cur = cur.right;
        }
    }
    return result;
}

二叉树专题的其他题目

查看二叉树全部题目 →