Độ sâu node lá cấp lẻ lớn nhất trong cây nhị phân trong C++

Giới thiệu

Tìm độ sâu lớn nhất của node lá (leaf node) nằm ở cấp độ lẻ (odd level) trong cây nhị phân. Cấp độ gốc = 1 (lẻ).

Ví dụ

Cây:

       1 (level 1)
      / \
     2   3 (level 2)
    /   / \
   4   5   6 (level 3)
      /     \
     7       8 (level 4)

Node lá cấp lẻ: 4 (level 3), 7 (level 4 - chẵn), 8 (level 4 - chẵn)

Chỉ node 4 ở cấp lẻ → độ sâu = 3

Mã nguồn hoàn chỉnh

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

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

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

int deepestOddLeafDepth(Node* root, int level) {
    if (root == NULL) return 0;
    
    // Nếu là node lá và cấp độ lẻ
    if (root->left == NULL && root->right == NULL && (level % 2 == 1)) {
        return level;
    }
    
    // Đệ quy tìm max ở hai cây con
    int left_depth = deepestOddLeafDepth(root->left, level + 1);
    int right_depth = deepestOddLeafDepth(root->right, level + 1);
    
    return max(left_depth, right_depth);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    
    cout << "Do sau node la cap le lon nhat: " 
         << deepestOddLeafDepth(root, 1) << endl;
    return 0;
}

Kết quả chạy chương trình

Do sau node la cap le lon nhat: 3

Phân tích độ phức tạp

• Thời gian: O(n) - thăm mỗi node một lần
• Không gian: O(h) - stack đệ quy, h = chiều cao cây

Phiên bản lặp (Iterative) dùng BFS

int deepestOddLeafBFS(Node* root) {
    if (!root) return 0;
    
    queue> q;
    q.push({root, 1});
    int max_odd_depth = 0;
    
    while (!q.empty()) {
        auto [node, level] = q.front(); q.pop();
        
        if (!node->left && !node->right && (level % 2 == 1)) {
            max_odd_depth = max(max_odd_depth, level);
        }
        
        if (node->left) q.push({node->left, level + 1});
        if (node->right) q.push({node->right, level + 1});
    }
    return max_odd_depth;
}

Kết luận

Bài toán biến thể của tìm độ sâu cây nhị phân, thêm điều kiện lọc node lá ở cấp lẻ. Cả đệ quy và BFS đều O(n).