🌲 二叉树

树的递归、DFS/BFS、BST 性质利用，是面试中最高频的数据结构之一。

15 题  ·  简单 ×6  中等 ×8  困难 ×1

核心思路

• 层序遍历：BFS，队列每次处理一整层（循环前记录队列大小）。
• 验证 BST：中序遍历应严格递增；或递归传入 (min, max) 约束范围。
• 路径总和 III：前缀和 + 哈希表（类似「和为 K 的子数组」的树上版本）。
• 最近公共祖先：若 p、q 分别在左右子树则当前节点即 LCA；否则向包含两者的子树递归。
• 构造二叉树：前序第一个是根，在中序中找根位置分割左右子树，递归建树（哈希表加速查找）。
• 最大路径和：后序遍历，每个节点计算「经过该节点的最大贡献值」（可向上传递），维护全局最大。
• 展开为链表：Morris 遍历思路：将左子树的最右节点接到右子树头，再把左子树移到右边，迭代处理。