难度: Medium
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。
示例 1：
输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1] 输出：3 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
示例 2：
输入：root = [1,1,1,null,1,null,null,1,1,null,1] 输出：4 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
示例 3：
输入：root = [1] 输出：0
提示：
50000 个节点。[1, 100] 之间。运行时间: 348 ms
内存: 61.5 MB
# 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:
longest = 0
def dfs(root, depth, isLeft):
nonlocal longest
longest = max(longest, depth)
if root is None:
return
if isLeft:
dfs(root.left, depth+1, False)
dfs(root.right, 0, True)
else:
dfs(root.right, depth+1, True)
dfs(root.left, 0, False)
dfs(root.right, 0, True)
dfs(root.left, 0, False)
return longest
本题解采用了深度优先搜索（DFS）的方法来解决二叉树的最长交错路径问题。首先定义一个全局变量 `longest` 来存储目前找到的最长路径长度。接着，定义一个递归函数 `dfs` 来探索每个节点，该函数接受当前节点、当前路径的长度 `depth`，以及一个布尔值 `isLeft` 指示当前的方向（左或右）。函数中，首先更新 `longest` 为当前路径长度和 `longest` 的较大值。如果当前节点为 `None`，则直接返回。根据当前的方向，递归调用左子或右子节点，并调换方向。最后，从根节点的左子和右子开始分别调用 `dfs` 函数，初始化方向分别为左和右，以探索所有可能的交错路径。最终，返回 `longest` 作为结果。
时间复杂度: O(n)
空间复杂度: O(h)
# 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:
longest = 0 # 用于存储最长路径长度
def dfs(root, depth, isLeft):
nonlocal longest
longest = max(longest, depth) # 更新最长路径长度
if root is None:
return
if isLeft:
dfs(root.left, depth+1, False) # 向左走并改变方向
dfs(root.right, 0, True) # 从当前节点重新开始向右
else:
dfs(root.right, depth+1, True) # 向右走并改变方向
dfs(root.left, 0, False) # 从当前节点重新开始向左
dfs(root.right, 0, True) # 从根节点的右子开始向右的路径
dfs(root.left, 0, False) # 从根节点的左子开始向左的路径
return longest # 返回最长路径长度
在递归函数中，路径长度depth的增加反映了当前节点到其子节点的有效交错路径的延伸。每次递归调用时改变方向并增加depth，是为了模拟交错路径的连续性。当重新开始一个方向时，depth被重置为0，是因为你正在从新的节点开始探索新的交错路径，因此需要重新计算路径长度。这样做是为了确保每个节点都可以作为交错路径的起点，以发现可能的更长路径。
在递归过程中，当遇到叶子节点（即没有子节点的节点），函数会检查当前节点，更新最长路径长度后，因为无子节点可递归，所以递归调用将结束。叶子节点作为路径的终点，其存在是至关重要的，因为它们代表了路径的结束。虽然它们不会直接延伸路径，但它们在计算最长路径时起到了关键角色，因为路径的长度在达到叶子节点时达到最大值。
使用全局变量`longest`在单线程环境下没有问题，但在多线程环境中，多个线程可能会同时修改这个变量，导致数据竞态和不一致的情况。作为替代方案，可以考虑使用线程局部存储来保持每个线程的`longest`副本，或者在每个线程完成后使用锁或其他同步机制来合并结果。另一种方法是避免使用全局变量，改用递归函数返回当前最长路径的长度，并通过参数传递来累加或比较长度。
递归函数`dfs`没有返回值是因为它通过修改外部变量`longest`来间接记录状态。这种设计简化了状态管理，但有时可能不是最高效的做法。通过让`dfs`返回当前节点的最长路径长度，我们可以避免使用全局变量，并可能提高代码的清晰性和效率。这样，每个递归调用都会贡献其子树的最长路径长度，可以在每个节点处更有效地比较和合并路径长度。