LeetCode 1372. 二叉树中的最长交错路径

字数 2408 2025-12-17 14:59:48

LeetCode 1372. 二叉树中的最长交错路径

题目描述
给你一棵以 root 为根的二叉树，二叉树中的「交错路径」定义如下：

选择二叉树中任意节点和一个方向（向左或者向右）。
如果前进方向为右，则移动到当前节点的右子节点；否则移动到左子节点。
改变前进方向：左变右或右变左。
这样一直交替进行，直到无法继续移动为止。

这条路径的长度定义为经过的节点数减 1（即边的数量）。
请你返回给定树中最长交错路径的长度。

示例 1：
输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出：3
解释：最长交错路径为 1（起点）-> 4（左）-> 5（右）-> 1（左），长度为 3。

解题过程

理解问题核心
我们需要在二叉树中找到一条最长的路径，这条路径的移动方向每一步都必须和上一步相反（左→右→左… 或右→左→右…）。路径可以从任意节点开始，沿着子节点方向交替移动，直到无法继续（没有对应方向的子节点）。注意路径的“长度”是边的数量，即节点数减 1。
思路分析
因为路径方向是交替的，我们可以为每个节点定义两个状态：
- left_max：表示从该节点出发，第一步向左走能形成的最长交错路径长度（边的数量）。
- right_max：表示从该节点出发，第一步向右走能形成的最长交错路径长度。
那么，对于某个节点：
- 如果它有左子节点，从它出发第一步向左，则下一步必须向右，所以 left_max = 1 + right_max_of_left_child。
- 如果它有右子节点，从它出发第一步向右，则下一步必须向左，所以 right_max = 1 + left_max_of_right_child。
- 如果没有对应的子节点，则对应的 left_max 或 right_max 为 0（因为无法走第一步）。
整个树的最长交错路径，就是所有节点的 left_max 和 right_max 中的最大值。
递归设计
我们可以用深度优先搜索（DFS）遍历树，在遍历过程中，对每个节点计算其 left_max 和 right_max，并更新全局最大值。递归函数可以返回一个二元组 (left_max, right_max) 给父节点使用。
详细步骤
1. 初始化全局变量 max_len = 0 记录答案。
2. 从根节点开始 DFS：
  - 如果当前节点为空，返回 (0, 0)。
  - 递归计算左子节点的 (left_left_max, left_right_max)。
  - 递归计算右子节点的 (right_left_max, right_right_max)。
  - 当前节点的 left_max：
    - 如果有左子节点：left_max = 1 + left_right_max（因为第一步向左，下一步必须向右，所以用左子节点的 right_max）。
    - 否则 left_max = 0。
  - 当前节点的 right_max：
    - 如果有右子节点：right_max = 1 + right_left_max（因为第一步向右，下一步必须向左，所以用右子节点的 left_max）。
    - 否则 right_max = 0。
  - 更新 max_len = max(max_len, left_max, right_max)。
  - 返回 (left_max, right_max) 给父节点。
3. 遍历结束后，返回 max_len。
示例推导
以题目示例的树（用数组表示）为例，我们模拟计算几个关键节点：
- 叶子节点：left_max = 0, right_max = 0。
- 节点 5（值为 1，左子节点为 1，右子节点为 1）：
  - 左子节点是叶子，其 right_max = 0 → 节点 5 的 left_max = 1 + 0 = 1。
  - 右子节点是叶子，其 left_max = 0 → 节点 5 的 right_max = 1 + 0 = 1。
- 节点 4（值为 1，左子节点为空，右子节点为 5）：
  - 无左子节点 → left_max = 0。
  - 右子节点是 5，其 left_max = 1 → 节点 4 的 right_max = 1 + 1 = 2。
- 根节点 1（值为 1，左子节点为空，右子节点为 4）：
  - 无左子节点 → left_max = 0。
  - 右子节点是 4，其 left_max = 0 → 节点 1 的 right_max = 1 + 0 = 1。
    但实际上最长路径是 1 → 4（左）→ 5（右）→ 1（左），长度为 3，这对应于从节点 4 出发的路径：4（左到 5）→ 5（右到 1）→ 1（左到空），长度为 3。计算时节点 4 的 left_max 应为：有左子节点 5，5 的 right_max = 1，所以 left_max = 1 + 1 = 2；节点 4 的 right_max 前面算得 2；所以节点 4 的最大值是 2。等等，这里似乎示例中的路径不是从单个节点开始的？实际上，路径 1→4→5→1 是从节点 1 开始的，但第一步方向是右（到 4），然后左（到 5），然后右（到 1）。计算节点 1 的 right_max 时，右子节点 4 的 left_max 是 2，所以 right_max = 1 + 2 = 3，这正是答案。
复杂度
时间复杂度 O(n)，每个节点访问一次。空间复杂度 O(h)，h 是树高，即递归栈深度。
关键点
- 状态定义：每个节点记录两个方向的最长长度。
- 状态转移：利用子节点的相反方向长度进行递推。
- 全局最大值：在递归过程中不断更新。

LeetCode 1372. 二叉树中的最长交错路径题目描述给你一棵以 root 为根的二叉树，二叉树中的「交错路径」定义如下：选择二叉树中任意节点和一个方向（向左或者向右）。如果前进方向为右，则移动到当前节点的右子节点；否则移动到左子节点。改变前进方向：左变右或右变左。这样一直交替进行，直到无法继续移动为止。这条路径的长度定义为经过的节点数减 1（即边的数量）。请你返回给定树中最长交错路径的长度。示例 1：输入：root = [ 1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1 ] 输出：3 解释：最长交错路径为 1（起点）-> 4（左）-> 5（右）-> 1（左），长度为 3。解题过程理解问题核心我们需要在二叉树中找到一条最长的路径，这条路径的移动方向每一步都必须和上一步相反（左→右→左… 或右→左→右…）。路径可以从任意节点开始，沿着子节点方向交替移动，直到无法继续（没有对应方向的子节点）。注意路径的“长度”是边的数量，即节点数减 1。思路分析因为路径方向是交替的，我们可以为每个节点定义两个状态： left_max ：表示从该节点出发，第一步向左走能形成的最长交错路径长度（边的数量）。 right_max ：表示从该节点出发，第一步向右走能形成的最长交错路径长度。那么，对于某个节点：如果它有左子节点，从它出发第一步向左，则下一步必须向右，所以 left_max = 1 + right_max_of_left_child 。如果它有右子节点，从它出发第一步向右，则下一步必须向左，所以 right_max = 1 + left_max_of_right_child 。如果没有对应的子节点，则对应的 left_max 或 right_max 为 0（因为无法走第一步）。整个树的最长交错路径，就是所有节点的 left_max 和 right_max 中的最大值。递归设计我们可以用深度优先搜索（DFS）遍历树，在遍历过程中，对每个节点计算其 left_max 和 right_max ，并更新全局最大值。递归函数可以返回一个二元组 (left_max, right_max) 给父节点使用。详细步骤初始化全局变量 max_len = 0 记录答案。从根节点开始 DFS：如果当前节点为空，返回 (0, 0) 。递归计算左子节点的 (left_left_max, left_right_max) 。递归计算右子节点的 (right_left_max, right_right_max) 。当前节点的 left_max ：如果有左子节点： left_max = 1 + left_right_max （因为第一步向左，下一步必须向右，所以用左子节点的 right_max ）。否则 left_max = 0 。当前节点的 right_max ：如果有右子节点： right_max = 1 + right_left_max （因为第一步向右，下一步必须向左，所以用右子节点的 left_max ）。否则 right_max = 0 。更新 max_len = max(max_len, left_max, right_max) 。返回 (left_max, right_max) 给父节点。遍历结束后，返回 max_len 。示例推导以题目示例的树（用数组表示）为例，我们模拟计算几个关键节点：叶子节点： left_max = 0, right_max = 0 。节点 5（值为 1，左子节点为 1，右子节点为 1）：左子节点是叶子，其 right_max = 0 → 节点 5 的 left_max = 1 + 0 = 1 。右子节点是叶子，其 left_max = 0 → 节点 5 的 right_max = 1 + 0 = 1 。节点 4（值为 1，左子节点为空，右子节点为 5）：无左子节点 → left_max = 0 。右子节点是 5，其 left_max = 1 → 节点 4 的 right_max = 1 + 1 = 2 。根节点 1（值为 1，左子节点为空，右子节点为 4）：无左子节点 → left_max = 0 。右子节点是 4，其 left_max = 0 → 节点 1 的 right_max = 1 + 0 = 1 。但实际上最长路径是 1 → 4（左）→ 5（右）→ 1（左），长度为 3，这对应于从节点 4 出发的路径：4（左到 5）→ 5（右到 1）→ 1（左到空），长度为 3。计算时节点 4 的 left_max 应为：有左子节点 5，5 的 right_max = 1 ，所以 left_max = 1 + 1 = 2 ；节点 4 的 right_max 前面算得 2；所以节点 4 的最大值是 2。等等，这里似乎示例中的路径不是从单个节点开始的？实际上，路径 1→4→5→1 是从节点 1 开始的，但第一步方向是右（到 4），然后左（到 5），然后右（到 1）。计算节点 1 的 right_max 时，右子节点 4 的 left_max 是 2，所以 right_max = 1 + 2 = 3 ，这正是答案。复杂度时间复杂度 O(n)，每个节点访问一次。空间复杂度 O(h)，h 是树高，即递归栈深度。关键点状态定义：每个节点记录两个方向的最长长度。状态转移：利用子节点的相反方向长度进行递推。全局最大值：在递归过程中不断更新。