1372. Longest ZigZag Path in a Binary Tree

解題思路

遍歷整棵樹，然後不斷更新當下的 zigzag 長度與整棵樹最常 zigzag 長度。

程式碼

原本的程式

class Solution {
public:
    void helper(TreeNode* root, bool lastIsLeft, int currentL, int& maxL)
    {
        if(root == nullptr)
            return;

        maxL = max(maxL, currentL);
        if(lastIsLeft)
        {
            helper(root->left, true, 1, maxL);
            helper(root->right, false, currentL + 1, maxL);
        }
        else
        {
            helper(root->left, true, currentL + 1, maxL);
            helper(root->right, false, 1, maxL);
        }

    }
    int longestZigZag(TreeNode* root) {
        int maxL = 0;
        helper(root->left, true, 1, maxL);
        helper(root->right, false, 1, maxL);
        return maxL;
    }
};

chatGPT 改進後的程式

class Solution {
public:
    void helper(TreeNode* root, int leftLen, int rightLen, int& maxLen) {
        if (root == nullptr) {
            return;
        }
        maxLen = max(maxLen, max(leftLen, rightLen));
        helper(root->left, rightLen + 1, 0, maxLen);
        helper(root->right, 0, leftLen + 1, maxLen);
    }

    int longestZigZag(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int maxLen = 0;
        helper(root, 0, 0, maxLen);
        return maxLen;
    }
};