第 10 站 · 链表与树

二叉树遍历与结构

按层 BFS 时间 O(n) · 空间 O(最大层宽)

周赛难度分难度分 1676–难度分 1703· 中位难度分 1690（2/26 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 10 站 · 26 题

先学: 链表
学完去: 树上路径
树的构造
二叉搜索树
网格搜索
回溯枚举
字典树序列化
面试频次: 9 家公司考过 · 面经出现 24 次Meta 10、Amazon 3、LinkedIn 3、Microsoft 2、TikTok / ByteDance 2

先做这道

LC 144二叉树的前序遍历简单

卡住再看

前序遍历建立递归与显式栈的对应关系。

要点

每一轮先记下队列长度，正好处理这么多个结点，层与层就分开了。
写递归 DFS 前先想清楚「子树返回什么」：深度、是否平衡、结点数，都是把左右两边的结果合并。
前序、中序、后序的区别只在于「处理当前结点」放在两次递归的前面、中间还是后面。

易错点

用一直在变化的队列长度当循环上界，会把下一层的结点也算进这一层。
Python 用 list.pop(0) 当队列是 O(n) 的，要用 collections.deque。
树退化成链时递归深度能到 10^5，Python 会爆栈；改成迭代或调高 recursionlimit。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

二叉树遍历 · 栈与队列

前序、中序、后序、层序遍历这棵树

换个输入

当前处理已发现 / 已计算答案

栈底 → 栈顶，或队首 → 队尾

空

遍历: 前序
输出: —

同一棵树，四种遍历顺序。节点下的 #k 是它在当前遍历里第几个输出。

速度

步骤 1 / 59

始终成立深度优先的三种顺序只差在「输出根」排在左右子树的前、中、后；层序用队列，先进先出就是一层一层。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 144。

Python

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def level_order(root) -> list[list[int]]:
    if not root:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):  # exactly the nodes of this level
            node = q.popleft()
            level.append(node.val)
            for child in (node.left, node.right):
                if child:
                    q.append(child)
        levels.append(level)
    return levels

C++

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    queue<TreeNode*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        levels.emplace_back();
        for (int k = q.size(); k > 0; k--) {  // exactly the nodes of this level
            TreeNode* node = q.front();
            q.pop();
            levels.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return levels;
}

Java

class TreeNode {
    int val;
    TreeNode left, right;

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

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

class Solution {
    List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int k = q.size(); k > 0; k--) { // exactly the nodes of this level
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            levels.add(level);
        }
        return levels;
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	var levels [][]int
	var q []*TreeNode
	if root != nil {
		q = append(q, root)
	}
	for len(q) > 0 {
		var level []int
		var next []*TreeNode // the following level
		for _, node := range q {
			level = append(level, node.Val)
			if node.Left != nil {
				next = append(next, node.Left)
			}
			if node.Right != nil {
				next = append(next, node.Right)
			}
		}
		levels = append(levels, level)
		q = next
	}
	return levels
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

后序求高度，用 -1 表示「已经不平衡」时间 O(n) · 递归深度 O(h)

判断要用到子树信息（是否平衡、高度、直径）时，后序遍历让每个结点先拿到左右子树的结果再算自己；用 -1 这种不可能的高度把「失败」一路传上去，不必再算一遍。LC 110 平衡二叉树、LC 104 最大深度、LC 543 二叉树的直径都是这个形状。

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def is_balanced(root) -> bool:
    """Every node's two subtree heights differ by at most 1 (LC 110)."""

    def height(node) -> int:  # -1 means "not balanced", passed straight up
        if not node:
            return 0
        left = height(node.left)
        if left < 0:
            return -1
        right = height(node.right)
        if right < 0 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return height(root) >= 0

C++

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Every node's two subtree heights differ by at most 1 (LC 110).
bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> height = [&](TreeNode* node) {  // -1 means "not balanced", passed straight up
        if (!node) return 0;
        int left = height(node->left);
        if (left < 0) return -1;
        int right = height(node->right);
        if (right < 0 || left - right > 1 || right - left > 1) return -1;
        return 1 + max(left, right);
    };
    return height(root) >= 0;
}

Java

class TreeNode {
    int val;
    TreeNode left, right;

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

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

class Solution {
    // Every node's two subtree heights differ by at most 1 (LC 110).
    boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    // -1 means "not balanced", passed straight up.
    private int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        if (left < 0) return -1;
        int right = height(node.right);
        if (right < 0 || Math.abs(left - right) > 1) return -1;
        return 1 + Math.max(left, right);
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// isBalanced reports whether every node's two subtree heights differ by at most 1 (LC 110).
func isBalanced(root *TreeNode) bool {
	var height func(node *TreeNode) int // -1 means "not balanced", passed straight up
	height = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := height(node.Left)
		if left < 0 {
			return -1
		}
		right := height(node.Right)
		if right < 0 || left-right > 1 || right-left > 1 {
			return -1
		}
		return 1 + max(left, right)
	}
	return height(root) >= 0
}

用栈迭代：前序，以及反转得到后序时间 O(n) · 空间 O(h)～O(n)

树很深、怕递归爆栈，或者面试官要求不用递归：前序用一个栈，先压右孩子再压左孩子；后序按「根、右、左」走一遍再整体反转。中序的迭代写法见二叉搜索树那一站。LC 144、LC 145、LC 94。

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def preorder(root) -> list[int]:
    """Root, left, right without recursion (LC 144)."""
    res, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)  # pushed first, so it comes out after the left subtree
        if node.left:
            stack.append(node.left)
    return res


def postorder(root) -> list[int]:
    """Left, right, root: a root, right, left walk reversed (LC 145)."""
    res, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

C++

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Root, left, right without recursion (LC 144).
vector<int> preorder(TreeNode* root) {
    vector<int> res;
    vector<TreeNode*> stack;
    if (root) stack.push_back(root);
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        res.push_back(node->val);
        if (node->right) stack.push_back(node->right);  // pushed first, so it comes out after the left subtree
        if (node->left) stack.push_back(node->left);
    }
    return res;
}

// Left, right, root: a root, right, left walk reversed (LC 145).
vector<int> postorder(TreeNode* root) {
    vector<int> res;
    vector<TreeNode*> stack;
    if (root) stack.push_back(root);
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        res.push_back(node->val);
        if (node->left) stack.push_back(node->left);
        if (node->right) stack.push_back(node->right);
    }
    reverse(res.begin(), res.end());
    return res;
}

Java

class TreeNode {
    int val;
    TreeNode left, right;

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

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

class Solution {
    // Root, left, right without recursion (LC 144).
    List<Integer> preorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) stack.push(node.right); // pushed first, so it comes out after the left subtree
            if (node.left != null) stack.push(node.left);
        }
        return res;
    }

    // Left, right, root: a root, right, left walk reversed (LC 145).
    List<Integer> postorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// preorder walks root, left, right without recursion (LC 144).
func preorder(root *TreeNode) []int {
	var res []int
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val)
		if node.Right != nil {
			stack = append(stack, node.Right) // pushed first, so it comes out after the left subtree
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return res
}

// postorder walks left, right, root: a root, right, left walk reversed (LC 145).
func postorder(root *TreeNode) []int {
	var res []int
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val)
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	return res
}

为什么对

每轮开始时队列里恰好是同一层的全部节点：第 0 轮只有根；处理完这一层的 size 个节点后，新入队的正好是它们的全部孩子，也就是下一层。归纳可知层与层不会混在一起。
递归 DFS 的正确性是结构归纳：假设左右子树返回的值都正确，只要当前节点能用它们正确合并出自己的值，整棵树就正确；空树是基础情况。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

层序遍历我用队列，每一轮开始先记下队列长度，正好处理这么多个节点，这样一层和下一层不会混在一起：处理完这一层，队列里剩下的恰好是下一层。如果是 DFS，我先定义子树要返回什么，比如高度或是否平衡，再用左右子树的结果合并出当前节点，正确性靠结构归纳。每个节点访问一次，O(n)。

English

For level order I use a queue and record its length at the start of each round, then process exactly that many nodes, so one level never mixes with the next. After a round, the queue holds exactly the following level. For DFS, I first define what a subtree returns, such as its height or whether it is balanced, then combine the left and right results at the node, which is correct by structural induction. Every node is visited once, so it is O(n).

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/2）

每轮开始时队列里恰好是同一层的全部节点：第 0 轮只有根；处理完这一层的 size 个节点后，新入队的正好是它们的全部孩子，也就是下一层。归纳可知层与层不会混在一起。
递归 DFS 的正确性是结构归纳：假设左右子树返回的值都正确，只要当前节点能用它们正确合并出自己的值，整棵树就正确；空树是基础情况。

小测

5 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

5 道题

在 n 个节点、高度为 h 的二叉树上做递归 DFS，额外空间（调用栈）是？
- 总是 O(n)
- 总是 O(log n)
- O(h)：平衡时约 O(log n)，退化成链时 O(n)
- O(1)
满二叉树（每个节点要么有 0 个、要么有 2 个孩子）如果有 n 个内部节点，它有几个叶子？
- n
- 2n
- n - 1
- n + 1
要自底向上算出每棵子树的高度，需要先处理完左右子树再处理当前节点。这对应哪种 DFS 顺序？
- 前序
- 后序
- 层序
- 中序
树有 n 个节点、高度为 h。时间和额外空间分别是？
```
def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))
```
- O(n) 时间，O(h) 额外空间
- O(n²) 时间，O(n) 额外空间
- O(log n) 时间，O(1) 额外空间
- O(n log n) 时间，O(log n) 额外空间

在有 n 个节点的完全平衡二叉树上调用 balanced(root)，时间复杂度是？

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

def balanced(node):
    if not node:
        return True
    if abs(height(node.left) - height(node.right)) > 1:
        return False
    return balanced(node.left) and balanced(node.right)

O(log n)
O(n)
O(n log n)
O(n²)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

        levels.append(level)
    return levels

分档练习

本站在 500 路里的 26 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 12

#	题目	一句话思路
144	二叉树的前序遍历	前序遍历建立递归与显式栈的对应关系。
94	二叉树的中序遍历	中序遍历练习一路向左入栈及回到祖先的过程。
145	二叉树的后序遍历	后序遍历理解先完成子树再处理父节点的依赖。
104	二叉树的最大深度	用递归返回值计算树高，区分节点数和边数。
111	二叉树的最小深度	最小深度正确处理单侧子树为空的节点。
100	相同的树	同步遍历两棵树，比较结构和节点值。
101	对称二叉树	把对称性转化为镜像位置的成对递归。
226	翻转二叉树	递归交换左右子树，理解原地结构修改。
617	合并二叉树	合并两棵树时区分共同节点与单侧存在的分支。
404	左叶子之和	通过父子关系识别左叶子，避免把普通左节点计入。
102	二叉树的层序遍历	按层维护队列边界，为后续层序变形建立模板。
107	二叉树的层序遍历 II	在层序遍历基础上调整结果组织，避免混淆节点与层次顺序。

核心 10

#	题目	一句话思路	难度分
103	二叉树的锯齿形层序遍历	按层交替输出方向，分离遍历顺序与展示顺序。
199	二叉树的右视图	从每层最后节点或右优先DFS提取右视图。
513	找树左下角的值	找最深层最左节点，维护遍历顺序和深度状态。
110	平衡二叉树	自底向上同时计算高度与平衡状态，避免重复遍历。
543	二叉树的直径	区分返回父节点的单支高度与经过当前节点的直径。
572	另一棵树的子树	分离寻找候选根和比较整棵子树的递归职责。
116	填充每个节点的下一个右侧节点指针	利用完美二叉树结构连接同层next指针。
222	完全二叉树的节点个数	利用完全二叉树左右边界高度加速节点计数。
958	二叉树的完全性检验	通过层序空缺后的节点约束验证完全二叉树。	难度分 1703
314	二叉树的垂直遍历 🔒	按列收集节点，利用BFS自然保留同列从上到下及同层顺序。

进阶 4

#	题目	一句话思路	难度分
117	填充每个节点的下一个右侧节点指针 II	在任意二叉树中构造下一层链，处理跨越空子树的连接。
662	二叉树最大宽度	给节点分配相对位置索引计算宽度，并控制索引增长。
987	二叉树的垂序遍历	区分列、行、值的多级排序，处理同一坐标的多个节点。	难度分 1676
545	二叉树的边界 🔒	把边界拆成左边界、叶子、逆序右边界，避免重复计数。

本站 OA 真题 9

Nested List Weight Sum (for E4)Meta
Sewer Drainage PartitionTwo Sigma
Maximum Time Required to Transfer DataRippling
Rooted Distances (Re-rooting DP)MathWorks
Chain of Command (Tree DFS Order, k-th Receiver)IMC
Tree PointsThe D. E. Shaw Group
Count Balanced Nodes in a TreeDeloitte
Minimum Flips to Match Expected Binary Values in a TreeUkg
Build Monuments其他

全部 9 道