Longest ZigZag Path in a Binary Tree ใน C++ : เส้นทาง ZigZag ยาวที่สุด

ให้ Binary Tree หา **ZigZag Path ยาวที่สุด** โดย:

• เริ่มที่ Node ใดก็ได้ เลือกทิศทาง (Left/Right)
• เดินตามทิศทาง -> **สลับทิศทาง** (Left<->Right) -> เดินต่อ -> สลับ... จนเดินไม่ได้
• ความยาว = จำนวน Nodes - 1 (Single Node = Length 0)

ตัวอย่าง

Tree Diagram (Right, Left, Right) -> Length 3

แนวทาง: DFS Return Pair (LeftMax, RightMax)

สำหรับแต่ละ Node คำนวณ:

• leftLen = Longest ZigZag เริ่มจาก Node นี้ **ไปซ้ายก่อน** (Next ต้องไป Right)
• rightLen = Longest ZigZag เริ่มจาก Node นี้ **ไปขวาก่อน** (Next ต้องไป Left)

Recurrence:

leftLen  = 1 + rightLen_of_left_child  (ถ้ามี Left Child)
rightLen = 1 + leftLen_of_right_child  (ถ้ามี Right Child)
Base: Leaf -> (0, 0) [Length 0 = 1 Node]
Null -> (-1, -1) เพื่อให้ 1 + (-1) = 0 สำหรับ Leaf Parent

Global Max = Max ของทุก leftLen และ rightLen

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxLen = 0;

    // Return {leftMax, rightMax} for this node
    pair<int, int> dfs(TreeNode* node) {
        if (!node) return {-1, -1}; // Null: -1 so 1+(-1)=0 for leaf parent

        auto [lLeft, lRight] = dfs(node->left);
        auto [rLeft, rRight] = dfs(node->right);

        // From this node: Go Left -> Next must Go Right (use lRight)
        int leftMax = 1 + lRight;
        // From this node: Go Right -> Next must Go Left (use rLeft)
        int rightMax = 1 + rLeft;

        maxLen = max({maxLen, leftMax, rightMax});

        return {leftMax, rightMax};
    }

    int longestZigZag(TreeNode* root) {
        dfs(root);
        return maxLen;
    }
};

Input / Output

Input:  [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3

ความซับซ้อน (Complexity)

• Time: O(N) — Visit ทุก Node 1 ครั้ง
• Space: O(H) — Recursion Stack

จุดสำคัญ

• Return Pair (LeftStart, RightStart) จาก Subtree
• Null Return {-1,-1} ทำให้ Leaf ได้ Length 0 (1 + -1 = 0) สวยงาม
• Global Variable maxLen Track คำตอบ

LeetCode 1372 ครับ