What is the core pattern in Binary Tree Inorder Traversal?

The pattern is binary-tree traversal with state tracking: go as far left as possible, record the node only after returning, then move right. The challenge is preserving that delayed visit order without losing where to come back.

Why does the example root = [1,null,2,3] return [1,3,2]?

Node 1 has no left child, so it is recorded first. Then you move to 2, but inorder requires finishing 2’s left subtree before visiting 2 itself, so 3 must be added before 2.

Is recursion acceptable for this problem?

Yes. For this Easy problem, recursion is usually the cleanest first answer because inorder maps directly to left, node, right. Just be ready to mention that recursion uses call-stack space, so it does not satisfy the strict O(1) follow-up.

When should I use Morris traversal here?

Use Morris traversal when the interviewer explicitly asks for constant extra space or points to the provided O(1) space complexity. It avoids both recursion and an explicit stack by temporarily threading each node’s inorder predecessor back to the current node.

How do I know my iterative stack solution is correct?

Your stack solution is correct if every node is pushed while walking left, popped exactly once, appended immediately after pop, and followed by a move into its right subtree. Any other order usually skips nodes or records them too early.

#94

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。示例 1：输入： root = [1,null,2,3] 输出： [1,3,2] 示例 2：输入： root = [] 输出： [] 示例 3：输入： root = [1] 输出： [1] 提示：树中节点数目在范围 [0, 10…

栈树深度优先搜索二叉树

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

lightbulb

解题思路

方法一：递归遍历

我们先递归左子树，再访问根节点，接着递归右子树。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Do you know why inorder on [1,null,2,3] must delay visiting 2 until after processing 3?
question_mark
Can you explain how your traversal keeps track of where to return after finishing a left subtree?
question_mark
Will you switch from recursion or a stack to Morris traversal if constant extra space is requested?

warning

常见陷阱

外企场景

error
Appending a node value before fully traversing its left subtree, which turns the result into preorder-like output instead of inorder.
error
After popping a node from the stack, forgetting to move to its right child, which causes entire right-side segments to be skipped.
error
Implementing Morris traversal without restoring predecessor.right to null, leaving threads behind and producing duplicate visits or a modified tree.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the preorder traversal of the same binary tree using recursive, iterative, or Morris-style traversal changes.
arrow_right_alt
Return the postorder traversal, where the state-tracking becomes harder because the node is recorded after both subtrees.
arrow_right_alt
Implement inorder traversal iteratively without recursion, then explain how the answer changes if the interviewer requires O(1) extra space.

help

常见问题

外企场景

继续练习

#114 二叉树展开为链表 #144 二叉树的前序遍历 #145 二叉树的后序遍历