Độ dài đường đi tăng liên tiếp lớn nhất trong cây nhị phân (C++)

Cho cây nhị phân, tìm độ dài đường đi dài nhất gồm các nút có giá trị tăng liên tiếp (chênh lệch 1). Mỗi nút là đường đi độ dài 1.

Ví dụ: Cây gốc 10, con trái 11, con phải 9, ... → đường dài nhất (11,12,13) độ dài 3.

Phương pháp đệ quy

• Hàm solve(root, prev_data, prev_length):
  • Nếu root null → trả về prev_length.
  • Nếu root->val == prev_data+1 → tiếp tục đường đi, đệ quy trái/phải với prev_length+1, lấy max.
  • Ngược lại → bắt đầu đường mới độ dài 1 từ root, đệ quy trái/phải, lấy max với prev_length.
• Gọi ban đầu: solve(root, root->val-1, 0).

Ví dụ (C++)

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

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

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

int maxLen(TreeNode* root){
    if(!root) 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;
}

Đầu ra

3