二叉树笔记总结

一、两种思维模式

遍历二叉树，外部变量实现
分解为子问题

> 快排类似于前序遍历，归并类似于后序遍历

二、前/中/后序遍历的区别

核心：遍历位置决定它们能根据多少信息做判断

遍历方式	可用信息
前序	上一次传入的信息
中序	传入的信息 + 左子树
后序	左右子树 + 传参

三、以树的视角看 DP / 回溯 / DFS

算法	本质	关注点
DP	分治	整棵子树
回溯	遍历	树枝（路径）
DFS	遍历	单个节点

四、解题核心思路

1. 节点视角

> 如果单独抽出一个二叉树节点，它需要做什么事？需要在什么时候（前/中/后序）做？

2. DFS / 路径类问题

递归到底部
保存类似路径的，使用递归
用一个变量保存路径

3. 最近公共祖先（LCA）

使用递归思路，将问题拆分：永find(root,val1,val2) 若根节点val=val1或val2，那根节点就是lca 左右子树各找到一个，那root还是祖先只在一侧找到，结果在那一侧，返回（子树，val1，val2）

常见题型

在dfs中，一般为遍历和分解问题等题型在bfs中，显然只能遍历

代码

dfs

// 二叉树的遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

bfs

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 访问 cur 节点，同时知道它所在的层数
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // 把 cur 的左右子节点加入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

二叉树刷题总结