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

Tìm độ sâu (depth/level) lớn nhất của các **nút lá (leaf node)** nằm ở **cấp độ lẻ (odd level)** trong cây nhị phân. Cấp gốc (root) thường tính là cấp 1 (lẻ).

Ví dụ

Cây:
15 (Level 1 - Leaf? No)
/ \
33 18 (Level 2)
/ \
19 20 (Level 3 - Leaf: 19, depth 3 odd -> candidate)
/ \
28 29 (Level 4 - Leaf: 28, 29, depth 4 even -> ignore)

Kết quả: 3 (độ sâu của nút lá 19).

Phương pháp giải - DFS Đệ quy

Duyệt DFS, truyền tham số currentLevel (bắt đầu từ 1). Khi gặp nút lá (left==null && right==null):

• Nếu currentLevel % 2 != 0 (lẻ): Cập nhật maxDepth = max(maxDepth, currentLevel).

Chương trình C++

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

bool isLeaf(Node* node) {
    return node && !node->left && !node->right;
}

void dfsDeepestOddLeaf(Node* node, int level, int &maxDepth) {
    if (!node) return;
    
    if (isLeaf(node)) {
        if (level % 2 != 0) { // Level lẻ
            maxDepth = max(maxDepth, level);
        }
        return;
    }
    
    dfsDeepestOddLeaf(node->left, level + 1, maxDepth);
    dfsDeepestOddLeaf(node->right, level + 1, maxDepth);
}

int deepestOddLevelLeafDepth(Node* root) {
    int maxDepth = 0;
    dfsDeepestOddLeaf(root, 1, maxDepth); // Root level = 1
    return maxDepth; // Trả về 0 nếu không có nút lá cấp lẻ nào
}

int main() {
    Node* root = new Node(15);
    root->left = new Node(33);
    root->right = new Node(18);
    root->right->left = new Node(19);
    root->right->right = new Node(20);
    root->right->right->left = new Node(28);
    root->right->right->right = new Node(29);
    
    cout << "Do sau nut la cap le sau nhat: " << deepestOddLevelLeafDepth(root) << endl;
    return 0;
}

Đầu ra

Do sau nut la cap le sau nhat: 3