C++ Độ dài đường đi có số gấp nhiều nhất trong cây nhị phân

Cho cây nhị phân, tìm đường đi có số gấp (bends) nhiều nhất. Gấp là khi đường đi thay đổi hướng từ trái sang phải hoặc ngược lại.

Output: 6

Phương pháp giải

Duyệt tất cả đường đi từ gốc đến lá, theo dõi hướng trước đó. Nếu hướng thay đổi, tăng số gấp. Cập nhật kết quả khi đến lá.

Ví dụ minh họa

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

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->key = key;
    return node;
}

void maximumBends(Node* node, char dir, int bends, int* maxBends, int soFar, int* len) {
    if (!node) return;
    if (!node->left && !node->right) {
        if (bends > *maxBends) {
            *maxBends = bends;
            *len = soFar;
        }
    } else {
        if (dir == 'l') {
            maximumBends(node->left, 'l', bends, maxBends, soFar+1, len);
            maximumBends(node->right, 'r', bends+1, maxBends, soFar+1, len);
        } else {
            maximumBends(node->right, 'r', bends, maxBends, soFar+1, len);
            maximumBends(node->left, 'l', bends+1, maxBends, soFar+1, len);
        }
    }
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    root->right->left->right = newNode(1);
    root->right->left->right->left = newNode(9);

    int len=0, bends=0, maxBends=-1;
    if (!root) cout << "0\n";
    else {
        if (root->left) maximumBends(root->left, 'l', bends, &maxBends, 1, &len);
        if (root->right) maximumBends(root->right, 'r', bends, &maxBends, 1, &len);
        cout << len << "\n";
    }
    return 0;
}

Kết quả

4

Giải thích

Đệ quy duyệt tất cả đường đi gốc→lá, đếm gấp khi đổi hướng. Cập nhật maxBends và độ dài đường đi tương ứng khi đến lá.

Kết luận

Đã giải bài toán đường đi có nhiều gấp nhất bằng DFS đệ quy. Code C++ chuyển được sang Java, Python, C. Hy vọng hữu ích.