Binary Tree Longest Consecutive Sequence II – เส้นทางต่อเนื่องเพิ่ม/ลดใน C++

ปัญหา: Binary Tree Longest Consecutive Sequence II

หา ความยาวเส้นทางต่อเนื่อง (consecutive) ที่ยาวที่สุด ใน Binary Tree
- เส้นทางเพิ่ม: 1→2→3→4
- เส้นทางลด: 4→3→2→1
- เส้นทางอาจเป็น Child-Parent-Child (ไม่จำเป็นต้อง parent-child ตรงๆ)

ตัวอย่าง

    2
   / \
  1   3

Longest: 1→2→3 หรือ 3→2→1 → Length = 3

แนวทางแก้ปัญหา: Post-order DFS + Pair DP

State

แต่ละโหนดคืน pair<inc, dec>:

• inc = ความยาวเส้นทางเพิ่มที่ยาวที่สุด เริ่มจากโหนดนี้ลงไป
• dec = ความยาวเส้นทางลดที่ยาวที่สุด เริ่มจากโหนดนี้ลงไป

Transitions

สำหรับลูกซ้ายและลูกขวา:

• ถ้า child->val == node->val + 1 → inc = max(inc, 1 + child.inc)
• ถ้า child->val == node->val - 1 → dec = max(dec, 1 + child.dec)

Global answer: max(ans, inc + dec - 1) (รวม inc+dec ผ่านโหนดนี้ ลบ 1 เพราะนับโหนดนี้ซ้ำ)

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

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

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

class Solution {
    int ans = 0;

    pair<int,int> dfs(TreeNode* node) {
        if (!node) return {0, 0};

        auto left = dfs(node->left);
        auto right = dfs(node->right);

        pair<int,int> cur = {1, 1}; // inc, dec

        // Check left child
        if (node->left) {
            if (node->left->val == node->val + 1)
                cur.first = max(cur.first, 1 + left.first);
            if (node->left->val == node->val - 1)
                cur.second = max(cur.second, 1 + left.second);
        }

        // Check right child
        if (node->right) {
            if (node->right->val == node->val + 1)
                cur.first = max(cur.first, 1 + right.first);
            if (node->right->val == node->val - 1)
                cur.second = max(cur.second, 1 + right.second);
        }

        // Path through this node (inc + dec - 1)
        ans = max(ans, cur.first + cur.second - 1);

        return cur;
    }

public:
    int longestConsecutive(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

int main() {
    Solution ob;
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    cout << ob.longestConsecutive(root); // 3
    return 0;
}

ความซับซ้อน

• เวลา: O(N) – เยี่ยมทุกโหนด 1 ครั้ง
• พื้นที่: O(H) – recursion stack

ข้อสังเกต

• LeetCode 549
• ต่างจาก LC 298 (Longest Consecutive Sequence) ที่ต้องเป็น parent-child เท่านั้น
• Pair DP เก็บ inc/dec แยกกัน → รวมได้ที่โหนดปัจจุบัน
• โค้ดต้นฉบับมีบั๊กเล็กน้อย: left = solveUtil(left) เขียนซ้ำ 2 ครั้ง (ควรเป็น left/right)