Binary Tree Longest Consecutive Sequence - Dãy liên tiếp dài nhất trong cây nhị phân

Cho cây nhị phân, tìm độ dài đường đi liên tiếp dài nhất (giá trị tăng 1 theo cha→con). Đường đi từ nút bất kỳ đến nút con cháu.

Ví dụ: cây có đường 3-4-5 → kết quả 3.

Giải thuật (DFS)

DFS truyền tham số prev (giá trị cha) và len (độ dài hiện tại). Nếu node.val == prev + 1, tăng len, cập nhật kết quả. Ngược lại reset len = 1. Gọi đệ quy cho hai con.

Cài đặt C++

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

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

class Solution {
public:
    int ans = 1;

    void solveUtil(TreeNode* node, int prev, int len = 1) {
        if (!node) return;
        if (prev + 1 == node->val) {
            len++;
            ans = max(ans, len);
            solveUtil(node->left, node->val, len);
            solveUtil(node->right, node->val, len);
        } else {
            solveUtil(node->left, node->val, 1);
            solveUtil(node->right, node->val, 1);
        }
    }

    int longestConsecutive(TreeNode* root) {
        if (!root) return 0;
        solveUtil(root, INT_MIN);
        return ans;
    }
};

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

Đầu vào

TreeNode(1)->right=3->left=2, right=4->right=5

Đầu ra

3