思考:
1.每一個點都要走到 --> DFS
2.如何控制走的左右子點方向
3.如何判斷這個節點是父節點的右子還是左子

/**
 * 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 maxLength = 0; // 用於記錄最長交錯路徑的長度
    // dir 表示父點來的方向（0 為左，1 為右），
    // currLength 表示從父節點到當前節點的交錯路徑長度
    void solve(TreeNode* root, int dir, int currLength) {
        if (root == NULL){
            return; // 若節點為空，則返回
        } 
        // 更新最長交錯路徑長度為當前長度和 maxLength 中的較大值
        maxLength = max(maxLength, currLength);
        // 往左點走 方向設為 0, 如果上一個路徑是 1 的話代表條件成立 路徑長度+1 否則歸1
        solve(root->left, 0, dir ? currLength + 1 : 1);
        // 往右點走 方向設為 1, 如果上一個路徑是 0 的話代表條件成立 路徑長度+1 否則歸1
        solve(root->right, 1, dir ? 1 : currLength + 1);
    }
    int longestZigZag(TreeNode* root) {
        solve(root, 0, 0);
        return maxLength; 
    }
};

/**
 * 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 maxPath = 0;

    void DFS(TreeNode* root, int dir, int currL){
        if(root == NULL){
            return;
        }
        //紀錄最大路徑
        //來源相反就++而已
        maxPath = max(maxPath, currL);
        DFS(root->left, 0, dir ? currL +1 : 1);
        DFS(root->right, 1, dir ? 1 : currL +1);
    }

    int longestZigZag(TreeNode* root) {
        DFS(root, 0, 0);
        return maxPath;
    }
};