DEV Community

Woody
Woody

Posted on

LeetCode二叉树专题

当然可以,下面是你请求的内容:二叉树 & 二叉树遍历相关的 LeetCode 题目 + Python 实现 + 经典题目的伪代码,适合初学到面试强化阶段使用。


✅ 一、你必须掌握的「二叉树遍历」概念

遍历方式 递归顺序 非递归(栈)支持 BFS版本
前序遍历 根 → 左 → 右
中序遍历 左 → 根 → 右
后序遍历 左 → 右 → 根
层序遍历 一层一层从上到下 ✅(队列)


✅ 二、LeetCode 中和二叉树遍历相关的核心题单

🌱 基础遍历题(递归 & 栈 & 队列)

题号 题目 类型
144 Binary Tree Preorder Traversal 前序遍历
94 Binary Tree Inorder Traversal 中序遍历
145 Binary Tree Postorder Traversal 后序遍历
102 Binary Tree Level Order Traversal 层序遍历
107 Binary Tree Level Order Traversal II 自底向上层序
103 Binary Tree Zigzag Level Order Traversal 层序之字形
100 Same Tree 遍历比较结构和值
101 Symmetric Tree 递归判断对称
104 Maximum Depth of Binary Tree DFS计算最大深度
110 Balanced Binary Tree 判断是否平衡
111 Minimum Depth of Binary Tree BFS求最小深度

✅ 三、Python 实现:三种遍历(递归 + 栈 + 队列)

# 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
Enter fullscreen mode Exit fullscreen mode

✅ 1. 前序遍历(Preorder Traversal)

def preorder(root):
    res = []

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

    dfs(root)
    return res
Enter fullscreen mode Exit fullscreen mode

✅ 2. 中序遍历(Inorder Traversal)

def inorder(root):
    res = []

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

    dfs(root)
    return res
Enter fullscreen mode Exit fullscreen mode

✅ 3. 后序遍历(Postorder Traversal)

def postorder(root):
    res = []

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

    dfs(root)
    return res
Enter fullscreen mode Exit fullscreen mode

✅ 4. 层序遍历(Level Order Traversal)

from collections import deque

def levelOrder(root):
    if not root:
        return []

    queue = deque([root])
    res = []

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)

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

        res.append(level)

    return res
Enter fullscreen mode Exit fullscreen mode

✅ 四、常见经典二叉树题目伪代码(英文)


📌 1. [104] Maximum Depth of Binary Tree

function maxDepth(node):
    if node is null:
        return 0
    left = maxDepth(node.left)
    right = maxDepth(node.right)
    return max(left, right) + 1
Enter fullscreen mode Exit fullscreen mode

📌 2. [101] Symmetric Tree (Check if Mirror)

function isSymmetric(root):
    return isMirror(root.left, root.right)

function isMirror(left, right):
    if left == null and right == null:
        return true
    if left == null or right == null:
        return false
    if left.val != right.val:
        return false
    return isMirror(left.left, right.right) and isMirror(left.right, right.left)
Enter fullscreen mode Exit fullscreen mode

📌 3. [100] Same Tree

function isSameTree(p, q):
    if p == null and q == null:
        return true
    if p == null or q == null:
        return false
    if p.val != q.val:
        return false
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Enter fullscreen mode Exit fullscreen mode

📌 4. [112] Path Sum

function hasPathSum(node, target):
    if node == null:
        return false
    if node is leaf and node.val == target:
        return true
    return hasPathSum(node.left, target - node.val) or hasPathSum(node.right, target - node.val)
Enter fullscreen mode Exit fullscreen mode

✅ 五、进阶:二叉树题型拓展

分类 题目推荐
构建树 105. Build Tree from Preorder and Inorder
路径类 112, 113, 124(路径和)
递归套路 判断结构/值是否一样,树的最大最小深度
序列化 297. Serialize and Deserialize Binary Tree

✅ 六、进阶技巧

  • 递归模板(后序返回型,前序处理型)
  • BFS/DFS 选择
  • 辅助函数 + 拆解问题(Divide & Conquer)
  • 注意 base case
  • 回溯常出现在路径题中

需要我帮你生成**“二叉树刷题计划 + 路线图”**,或者手把手讲解某题递归如何思考?我可以配图或一步步 Debug 来讲。你想学哪种?

Top comments (0)