二叉树解题的思维模式：遍历与分解问题|dc的house

二叉树是数据结构中最常见的一种树形结构，广泛应用于算法设计和问题求解中。在解决二叉树相关问题时，通常有两种核心的思维模式：遍历和分解问题。本文将详细介绍这两种思维模式，并通过代码示例帮助读者深入理解如何应用它们解决实际问题。

一、二叉树的两种解题思维模式

1. 遍历的思维模式

核心思想：是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。

特点：
- 通过递归或迭代的方式遍历二叉树的每一个节点。
- 在遍历的过程中，通过外部变量记录所需的信息（如最大值、最小值、路径和等）。
- 适用于需要全局信息的问题。
适用场景：
- 计算二叉树的节点总数。
- 查找二叉树的最大深度。
- 判断二叉树是否为平衡二叉树。
关键点：
- 在遍历的过程中，需要在合适的位置（前序、中序、后序）更新外部变量。
- 遍历的顺序取决于问题的需求。

2. 分解问题的思维模式

核心思想：是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。

特点：
- 将问题分解为子问题，递归求解子问题的答案。
- 通过子问题的答案推导出原问题的答案。
- 适用于需要局部信息的问题。
适用场景：
- 计算二叉树的直径。
- 判断二叉树是否为二叉搜索树。
- 查找二叉树中某条路径的最大和。
关键点：
- 递归函数的返回值需要包含子问题的答案。
- 在递归的过程中，需要明确如何利用子问题的答案推导出原问题的答案。

二、遍历的思维模式详解

1. 遍历的基本框架

二叉树的遍历分为三种：

前序遍历：根节点 -> 左子树 -> 右子树。
中序遍历：左子树 -> 根节点 -> 右子树。
后序遍历：左子树 -> 右子树 -> 根节点。

以下是遍历的基本框架：

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

2. 遍历的应用示例

示例 1：计算二叉树的节点总数

int count = 0;

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置：访问当前节点
    count++;
    traverse(root->left);
    traverse(root->right);
}

int countNodes(TreeNode* root) {
    traverse(root);
    return count;
}

分析：
- 通过前序遍历访问每一个节点，并在访问时更新外部变量 count。
- 最终 count 即为二叉树的节点总数。

示例 2：查找二叉树的最大深度

int maxDepth = 0;
int currentDepth = 0;

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置：进入节点，深度加 1
    currentDepth++;
    if (root->left == nullptr && root->right == nullptr) {
        // 叶子节点，更新最大深度
        maxDepth = max(maxDepth, currentDepth);
    }
    traverse(root->left);
    traverse(root->right);
    // 后序位置：离开节点，深度减 1
    currentDepth--;
}

int findMaxDepth(TreeNode* root) {
    traverse(root);
    return maxDepth;
}

分析：
- 通过前序遍历记录当前深度，并在叶子节点处更新最大深度。
- 通过后序遍历恢复当前深度。

三、分解问题的思维模式详解

1. 分解问题的基本框架

分解问题的核心是定义一个递归函数，通过子问题的答案推导出原问题的答案。以下是基本框架：

ResultType dfs(TreeNode* root) {
    if (root == nullptr) {
        // 返回基准情况的结果
    }
    ResultType left = dfs(root->left);  // 递归求解左子树
    ResultType right = dfs(root->right); // 递归求解右子树
    // 后序位置：利用 left 和 right 推导当前节点的结果
    return result;
}

2. 分解问题的应用示例

示例 1：计算二叉树的直径

int maxDiameter = 0;

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftMax = maxDepth(root->left);
    int rightMax = maxDepth(root->right);
    // 后序位置：计算当前节点的直径
    int myDiameter = leftMax + rightMax;
    maxDiameter = max(maxDiameter, myDiameter);
    // 返回当前子树的最大深度
    return 1 + max(leftMax, rightMax);
}

int diameterOfBinaryTree(TreeNode* root) {
    maxDepth(root);
    return maxDiameter;
}

分析：
- 递归函数 maxDepth 返回当前子树的最大深度。
- 在后序位置计算当前节点的直径，并更新全局变量 maxDiameter。

示例 2：判断二叉树是否为平衡二叉树

bool isBalanced(TreeNode* root) {
    return dfs(root) != -1;
}

int dfs(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int left = dfs(root->left);
    int right = dfs(root->right);
    // 如果左右子树不平衡，或者当前节点不平衡，返回 -1
    if (left == -1 || right == -1 || abs(left - right) > 1) {
        return -1;
    }
    // 返回当前子树的最大深度
    return 1 + max(left, right);
}

分析：
- 递归函数 dfs 返回当前子树的最大深度。
- 如果子树不平衡，返回 -1。
- 通过返回值判断二叉树是否平衡。

四、两种思维模式的对比

特性	遍历的思维模式	分解问题的思维模式
核心思想	通过遍历获取全局信息	通过递归求解子问题
外部变量	需要外部变量记录信息	不需要外部变量
返回值	通常无返回值	返回子问题的结果
适用场景	需要全局信息的问题	需要局部信息的问题
代码复杂度	通常较简单	通常较复杂