1372. Longest ZigZag Path in a Binary Tree

📘 題目敘述

給你一棵二元樹的根節點 root。

ZigZag 路徑定義為：從某個節點開始，往下走到子節點的路徑，並且每一步的方向必須在「左、右、左、右……」之間交替。

更正式地說，如果目前一步走向左子節點，那下一步就必須走向右子節點；如果目前一步走向右子節點，那下一步就必須走向左子節點。

ZigZag 路徑的長度是路徑中邊（edges）的數量，也就是走的步數。單一節點的路徑長度為 0。

請回傳這棵樹中最長 ZigZag 路徑的長度。

條件限制

樹中節點的數量在範圍 [1, 5 * 10^4]
1 <= Node.val <= 100

🧠 解題思路

我把 ZigZag 想成一件事：

只要我知道「上一步走的是左還是右」，我就知道下一步必須走哪邊，並且可以更新目前連續 ZigZag 的長度。

所以我在 DFS 函式裡帶兩個狀態：

before：上一步走的方向（我用 true 表示上一步是走左邊，false 表示上一步走右邊）
count：目前連續 ZigZag 的長度（也就是目前已經走了幾條邊）

當我站在某個節點 root：

先用 ans = max(ans, count) 更新全域答案
如果上一步走左邊（before == true）：
- 下一步要走右邊才能延續 ZigZag：check(root->right, false, count + 1)
- 如果我走左邊，方向就沒交替，等於重新開始：check(root->left, true, 1)
如果上一步走右邊（before == false）：
- 下一步要走左邊才能延續：check(root->left, true, count + 1)
- 如果走右邊，代表重新開始：check(root->right, false, 1)

最後我在 longestZigZag 裡從根節點做兩次 DFS：

一次假設「上一動是左」（before = true）
一次假設「上一動是右」（before = false）

這樣就等於把「從根開始的所有可能 ZigZag 起手方向」都涵蓋到。

所有變數

root：題目輸入的樹根節點（也是 check 目前所在節點）
ans：目前找到的最長 ZigZag 長度（全域最大值）
before：上一條邊走的方向（true 表示上一動往左，false 表示上一動往右）
count：目前這條 ZigZag 路徑的長度（邊數）

🪜 主要流程步驟

1. 用 `check` 做 DFS，帶著「方向」與「目前長度」

check 的參數就是我維護 ZigZag 的狀態：上一動方向 + 目前連續長度。每往下走一次，就能決定是延續或重開。

2. 每到一個節點先更新答案

因為 count 代表「走到這個節點時的 ZigZag 長度」，所以我每次都先做：

ans = max(ans, count)

確保所有節點都能當作結尾被拿來更新最大值。

3. 用 before 決定哪個子節點是「延續」，哪個是「重開」

如果 before == true（上一動走左）
- 走右子樹是延續：長度 count + 1
- 走左子樹是重開：長度變成 1
如果 before == false（上一動走右）
- 走左子樹是延續：長度 count + 1
- 走右子樹是重開：長度變成 1

4. 從根節點起跑時做兩次，涵蓋兩種起手方向

因為根節點本身沒有「上一動」，所以我用兩次呼叫去模擬兩種可能的起手：

check(root, true, 0)
check(root, false, 0)

最後回傳 ans。

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    void check(TreeNode* root, bool before, int count) { // true是左邊
        if (root) {
            ans = max(ans, count);
            if (before) {
                check(root->right, false, count + 1);
                check(root->left, true, 1);
            } else {
                check(root->left, true, count + 1);
                check(root->right, false, 1);
            }
        } else {
            return;
        }
    }
    int longestZigZag(TreeNode* root) {
        check(root, true, 0);
        check(root, false, 0);
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/