Dãy liên tiếp dài nhất trong cây nhị phân II trong C++

Giới thiệu

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 hoặc giảm 1 mỗi bước). Đường đi có thể đi lên/xuống (con-cha-con), không nhất thiết cha-con.

Thuật toán: DFS trả về cặp (tăng, giảm)

Với mỗi nút, đệ quy tính:

• inc: độ dài đường tăng kết thúc tại nút này (từ con lên cha).
• dec: độ dài đường giảm kết thúc tại nút này.

Kết hợp: đường đi qua nút này = inc + dec - 1 (nút được đếm 2 lần). Cập nhật kết quả toàn cục.

Cài đặt 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 dfs(TreeNode* node) {
        if (!node) return {0,0};
        auto [incL, decL] = dfs(node->left);
        auto [incR, decR] = dfs(node->right);
        int inc = 1, dec = 1;
        if (node->left) {
            if (node->left->val == node->val + 1) inc = max(inc, 1 + incL);
            if (node->left->val == node->val - 1) dec = max(dec, 1 + decL);
        }
        if (node->right) {
            if (node->right->val == node->val + 1) inc = max(inc, 1 + incR);
            if (node->right->val == node->val - 1) dec = max(dec, 1 + decR);
        }
        ans = max({ans, inc, dec, inc + dec - 1});
        return {inc, dec};
    }
public:
    int longestConsecutive(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

int main() {
    // Cây: 2 / \ 1 3
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    Solution ob;
    cout << ob.longestConsecutive(root); // Output: 3 (1-2-3 hoặc 3-2-1)
    return 0;
}

Phân tích

• Thời gian: O(N) – mỗi nút thăm 1 lần.
• Không gian: O(H) – stack đệ quy.

LeetCode 549 "Binary Tree Longest Consecutive Sequence II".