222. Count Complete Tree Nodes
Tags:
Easy
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu đếm số node của một binary tree hoàn chỉnh (complete binary tree). Đặc điểm của cây hoàn chỉnh là: Mọi tầng (trừ tầng cuối) đều đầy đủ node, tầng cuối các node nằm sát trái
Approach
Thay vì duyệt qua từng node (O(n)), ta có thể tận dụng tính chất của cây hoàn chỉnh để giảm thời gian xuống O(logn ^2)
Time and space complexity
Vậy tổng thời gian:
Các thuật toán đệ quy trên cây nhị phân thông thường có SC: O(n), trong trường hợp cây nghiêng, nhưng với complete binary tree thì tối đa là O(logn)
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function countNodes(root: TreeNode | null): number {
16 function getDepth(node: TreeNode | null): number {
17 if (!node) return 0;
18 let depth = 0;
19 while (node) {
20 depth++
21 node = node.left;
22 }
23 return depth
24 }
25
26 if (!root) return 0;
27
28 let left_depth = getDepth(root.left);
29 let right_depth = getDepth(root.right);
30
31 if (left_depth === right_depth) {
32 return (1 << left_depth) + countNodes(root.right)
33 } else {
34 return (1 << right_depth) + countNodes(root.left)
35 }
36};(1 << left_depth) + countNode((root.right) left_depth tầng (tính từ node gốc của cây con bên trái)(1 << left_depth) đã bao gồm node gốc hiện tại, nên nó tính luôn cả node gốc.countNodes(root.right)