Career Prep 2027

Appearance

Tree / Binary Tree ​

目标：掌握秋招高频的二叉树结构、DFS/BFS、递归、BST 与完全二叉树；理解与 Stack / Queue / Heap 的联系，不扩展到低收益的高级树结构细节。

1. Binary Tree ​

二叉树要求：

每个节点最多有两个子节点。

普通二叉树不要求：

text
left < root < right

该顺序约束属于 Binary Search Tree（BST）。

Python 节点结构：

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

与链表的结构联系：

text
Linked List Node
= value + next

Binary Tree Node
= value + left + right

最重要的递归结构：

text
Tree
= Root
+ Left Subtree
+ Right Subtree

因此树天然适合递归处理。

2. DFS 与三种遍历 ​

统一 DFS 框架：

python
def dfs(node):
    if node is None:
        return

    # 前序位置
    dfs(node.left)

    # 中序位置
    dfs(node.right)

    # 后序位置

对应：

text
Preorder:  Root → Left → Right
Inorder:   Left → Root → Right
Postorder: Left → Right → Root

核心理解：

三种遍历本质上是同一个 DFS，只是处理当前节点的时机不同。

前序示例：

python
def preorder(node):
    if node is None:
        return

    print(node.val)
    preorder(node.left)
    preorder(node.right)

后序常见于“父节点答案依赖子树答案”的问题。

3. Recursive DFS vs Iterative DFS ​

递归 DFS：

系统通过 Call Stack 保存尚未执行完成的函数调用与返回位置。

Stack 是 LIFO，因此：

text
调用：A → B → D
返回：D → B → A

迭代 DFS 可以显式维护 Stack。

前序遍历：

python
def preorder_iterative(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        print(node.val)

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

如果希望先访问左子树，由于 Stack 是 LIFO，应：

text
先压 right
再压 left

这样 left 会先被 pop。

注意：

text
DFS
= 搜索策略

递归 / Stack
= 实现方式

4. DFS Complexity ​

若树有 n 个节点，每个节点访问一次：

text
Time: O(n)

递归调用栈深度取决于树高 h：

text
Space: O(h)

平衡树：

text
h ≈ O(log n)

退化树：

text
h = O(n)

所以不能看到两个递归调用就机械把复杂度相乘。

5. BFS / Level Order ​

BFS 按层访问：

text
第 1 层 → 第 2 层 → 第 3 层 → ...

使用 Queue，因为需要 FIFO：

text
DFS → Stack
BFS → Queue

Python 常用：

python
from collections import deque

基本 BFS：

python
from collections import deque

def bfs(root):
    if root is None:
        return

    queue = deque([root])

    while queue:
        node = queue.popleft()
        print(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

按层处理：

python
queue = deque([root])

while queue:
    level_size = len(queue)

    for _ in range(level_size):
        node = queue.popleft()

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

level_size 必须在当前层开始时固定，以区分当前层与处理过程中加入的下一层节点。

6. Maximum Depth ​

递归关系：

text
depth(root)
= max(depth(root.left), depth(root.right)) + 1

空树：

text
0

只有根节点：

text
1

代码：

python
def max_depth(root):
    if root is None:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return max(left_depth, right_depth) + 1

这是典型后序思想：

text
孩子结果 → 父节点结果

需要区分两个原因：

text
算法依赖关系：
父节点答案依赖左右子树答案

实现机制：
递归调用由 LIFO Call Stack 管理

“必须先算子树”根本原因是数据依赖，不是因为 Stack 本身是 LIFO。

BFS 也可以通过统计层数求最大深度。

7. Binary Search Tree (BST) ​

对任意节点：

text
左子树所有值 < 当前节点 < 右子树所有值

约束作用于整棵左右子树，而不只是直接孩子。

因此判断 BST 时，不能只比较父节点与直接孩子。

BST 查找：

text
target < node → left
target > node → right

只需沿一条路径，因此：

text
Time = O(h)

平衡时：

text
O(log n)

退化为链表时：

text
O(n)

BST 中序遍历得到有序序列，因为：

text
BST:     Left < Root < Right
Inorder: Left → Root → Right

8. BST vs Hash Table ​

text
Hash Table
→ 精确 key 查询平均 O(1)
→ 不擅长维护顺序和范围关系

BST
→ 查询 O(h)，平衡时约 O(log n)
→ 保留有序结构
→ 更适合顺序 / 范围类操作

例如：

text
查某个 key 是否存在
→ Hash 很强

查 20~50 范围、最小值、按序遍历
→ 有序 Tree 更自然

9. Perfect / Complete / Balanced Binary Tree ​

Perfect Binary Tree ​

每一层全部填满。

若根节点为第 1 层，高度为 h：

text
n = 2^h - 1

Complete Binary Tree ​

要求：

  • 除最后一层外，其余层全部填满；
  • 最后一层允许不满；
  • 最后一层节点必须从左到右连续排列，不能跳位置。

若用数组从下标 0 开始存储，节点 i：

text
left   = 2i + 1
right  = 2i + 2
parent = (i - 1) // 2

因为层序节点连续占据数组下标，父子关系可以直接由下标推导，所以无需为每个节点保存 left/right 指针。

这直接连接 Heap。

Balanced Binary Tree ​

平衡关注的是左右子树高度不要长期严重失衡，不要求节点全部填满。

严重退化：

text
A
 \
  B
   \
    C
     \
      D

此时树的高度接近 n，BST 查询也会退化到 O(n)。

AVL Tree / Red-Black Tree 都属于用于控制 BST 退化的自平衡树；当前秋招阶段只要求理解这一作用，不展开旋转和详细性质。

10. Core Connections ​

text
Binary Tree
│
├── DFS
│   ├── Recursive → Call Stack
│   └── Iterative → Explicit Stack
│
├── BFS / Level Order
│   └── Queue
│
├── BST
│   └── Ordering / Search / Range
│
└── Complete Binary Tree
    └── Compact Array Representation
        └── Heap

Review Focus ​

后续需要通过真实代码题继续强化：

  • DFS 递归返回过程；
  • 前中后序代码快速写出；
  • BFS 层序与 level_size；
  • 最大深度；
  • BST 整棵子树约束；
  • 图中的 DFS/BFS 复用。

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_2.md

Mistakes:

05_Mistakes/CS.md

Interview QA:

06_Interview/CS_QA/Data_Structure.md