Longest Zigzag Path In a Binary Tree

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

分析

路径的定义：
- 选择一个起始节点和方向：
  - 如果前进方向是右，则移动到右子节点
  - 如果前进方向是左，则移动到左子节点
- 每次移动后，改变方向继续前进
递归处理：
- 使用深度优先搜索（DFS）遍历整棵树
- 每次递归返回以：当前节点为起点的最长交错路径长度
方向参数：
- 每次递归调用带上方向参数 direction：
  - 0 表示上一次路径方向为左
  - 1 表示上一次路径方向为右
路径长度计算：
- 若当前节点移动方向为左，则当前路径长度为右子树返回值 + 1
- 若当前节点移动方向为右，则当前路径长度为左子树返回值 + 1
- 更新全局最大值 res

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(h)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution
{
public:
    int res = 0; // 全局变量记录最大交错路径长度

    int longestZigZag(TreeNode* root)
    {
        dfs(root, 0); // 从根节点开始递归，初始方向为左
        return res;
    }

    int dfs(TreeNode* root, int direction)
    {
        if (!root) // 空节点返回 0
            return 0;

        // 递归计算左右子树的交错路径
        int left = dfs(root->left, 0);  // 进入左子树，方向为左
        int right = dfs(root->right, 1); // 进入右子树，方向为右

        // 更新最长交错路径
        res = std::max(res, std::max(left, right));

        // 返回以当前节点为起点的路径长度
        if (direction == 0) // 当前方向为左
            return right + 1;
        return left + 1; // 当前方向为右
    }
};