Đếm Chi Nhánh Lá BIDV

Mô tả

Ngân hàng BIDV quản lý sơ đồ tổ chức theo cấu trúc cây nhị phân: mỗi chi nhánh có tối đa hai chi nhánh con — bên trái và bên phải. Sơ đồ này giúp Ban lãnh đạo dễ dàng theo dõi chuỗi quản lý từ Hội sở xuống tận các phòng giao dịch địa phương.

Cuối năm, phòng Nhân sự cần thống kê số lượng chi nhánh lá — tức những chi nhánh ở cấp thấp nhất, không còn chi nhánh con nào trực thuộc (cả bên trái lẫn bên phải đều trống). Đây chính là cơ sở để đánh giá độ phủ dịch vụ tại các địa phương.

Cho danh sách parents gồm n phần tử mô tả cây nhị phân: phần tử thứ i cho biết id của chi nhánh cha trực tiếp của chi nhánh i. Đặc biệt, giá trị -1 nghĩa là chi nhánh đó là gốc của cả cây, không có cha.

Nhiệm vụ: bạn hãy đếm tổng số chi nhánh lá trong cây.

Đầu vào

• Một mảng số nguyên parents gồm n phần tử, trong đó parents[i] là id của chi nhánh cha của chi nhánh i.

Đầu ra

• Trả về một số nguyên dương là số lượng chi nhánh lá trong cây.

Ràng buộc

• 1 ≤ n ≤ 10^5
• -1 ≤ parents[i] ≤ n - 1
• Đảm bảo dữ liệu đầu vào tạo thành đúng một cây nhị phân hợp lệ (có đúng một gốc, không có chu trình).
• Mỗi chi nhánh có tối đa hai chi nhánh con.

Ví dụ

Ví dụ 1:

Đầu vào: [-1, 0, 0, 1, 1, 2, 2]

Giải thích:

• Chi nhánh 0 là gốc (parents[0] = -1).
• Chi nhánh 0 có hai con: chi nhánh 1 và chi nhánh 2.
• Chi nhánh 1 có hai con: chi nhánh 3 và chi nhánh 4.
• Chi nhánh 2 có hai con: chi nhánh 5 và chi nhánh 6.