หา Maximum Consecutive Increasing Path Length ใน Binary Tree ใน C++

โจทย์

กำหนด Binary Tree หาความยาวเส้นทาง (path) ที่ยาวที่สุดที่ประกอบด้วยโหนดที่มีค่า consecutive increasing (เพิ่มขึ้นทีละ 1) ทุกโหนดนับเป็น path ยาว 1

ตัวอย่าง: ต้นไม้ที่มี path 11→12→13 → คำตอบ = 3

วิธีการแก้ปัญหา

Recursive DFS:

• ฟังก์ชัน solve(root, prev_data, prev_length):
  • Base case: root == NULL → return prev_length
  • cur_data = root->val
  • ถ้า cur_data == prev_data + 1 → per ต่อ path: return max(solve(left), solve(right)) ด้วย prev_length+1
  • มิฉะนั้น → เริ่ม path ใหม่: newPathLen = max(solve(left, cur_data, 1), solve(right, cur_data, 1)), return max(prev_length, newPathLen)
• Main: เรียก solve(root, root->val-1, 0)

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

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

int solve(TreeNode *root, int prev_data, int prev_length){
    if (!root) return prev_length;
    int cur_data = root->val;
    if (cur_data == prev_data+1){
        return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
    }
    int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
    return max(prev_length, newPathLen);
}

int maxLen(TreeNode *root){
    if (root == NULL) return 0;
    return solve(root, root->val-1, 0);
}

int main(){
    TreeNode *root = new TreeNode(10);
    root->left = new TreeNode(11);
    root->right = new TreeNode(9);
    root->left->left = new TreeNode(13);
    root->left->right = new TreeNode(12);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(8);
    cout << maxLen(root);
    return 0;
}

อินพุต

TreeNode *root = new TreeNode(10); root->left = new TreeNode(11); root->right = new TreeNode(9); root->left->left = new TreeNode(13); root->left->right = new TreeNode(12); root->right->left = new TreeNode(13); root->right->right = new TreeNode(8);

เอาต์พุต

3