1372. 二叉树中的最长交错路径 - Longest ZigZag Path in a Binary Tree

🎯 问题描述（来源于LeetCode）

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

从任意节点开始，每一步可以向左或向右，但不能连续两次向同一方向移动（即必须左右交替）。
路径长度定义为路径上的边数（非节点数）。

返回该树中最长交错路径的长度。

说明：

路径可以从任意节点开始，不一定从根节点开始。
如果树为空，返回 0。

示例：

示例 1：

1
2
3

输入: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
输出: 3
解释: 最长交错路径为 3 条边（如右-左-右）。

示例 2：

1 2	输入: root = [1,1,1,null,1,null,null,1,1,null,1] 输出: 4

💻 解题思路

思路1：DFS 传递方向步数

算法步骤

全局变量 ans 记录最长交错路径的长度（边数）。
定义递归函数 dfs(node, l, r)：
- l：当前节点向左走时能形成的交错路径长度（从父节点方向来，若父节点方向为右，则当前可向左形成 l 步）。
- r：当前节点向右走时能形成的交错路径长度。
- 参数含义：假设从父节点到达当前节点时，如果父节点方向是左，则当前 l 表示继续向左的长度为 0（因为不能连续左），r 表示转向右的长度为父节点传递的步数+1。具体实现中，我们传入的是「以当前节点为起点，向左右两个方向可以延伸的交错长度」。
- 实际代码中：dfs(node, l, r) 表示以当前节点为结束点，左方向累计步数为 l，右方向累计步数为 r。然后更新 ans 为 max(ans, l, r)。
递归终止条件：
- 如果 node 为 None，直接返回。
向子节点递归：
- 如果左子节点存在，调用 dfs(node.left, r + 1, 0)：
  因为从当前节点向左走，上一步的方向是右（r 代表了从上一步右方向来的长度），所以向左时可以延续 r+1；而向左后，再下一步不能继续向左，所以右方向参数为 0。
- 如果右子节点存在，调用 dfs(node.right, 0, l + 1)：
  对称地，向右走时，上一步方向是左（l），所以右方向长度 l+1；左方向参数为 0。
启动递归：dfs(root, 0, 0)，初始时没有上一步方向，两个方向均为 0。
返回 ans。

思路1：代码实现

# 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
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, l, r):
            if node is None:
                return
            nonlocal ans
            ans = max(ans, l, r)
            if node.left:
                dfs(node.left, r + 1, 0)
            if node.right:
                dfs(node.right, 0, l + 1)
        dfs(root, 0, 0)
        return ans