1530. Number of Good Leaf Nodes Pairs
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đây là dạng problem liên quan đến tree traversal và tính toán distance between two leafs
Approach
1. Sử dụng Depth-First Search (DFS)
DFS là phương pháp phù hợp để duyệt cây nhị phân vì nó cho phép bạn khám phá toàn bộ các nhánh của cây một cách hiệu quả.
2. Chia để trị (Divide and Conquer)
Phương pháp này chia bài toán thành các bài toán con nhỏ hơn:
3. Tính khoảng cách giữa các nút lá
Khoảng cách giữa hai nút lá được tính bằng tổng độ sâu của chúng cộng thêm 2 (để đi qua nút cha chung). Bạn chỉ cần kiểm tra những cặp có tổng độ sâu nhỏ hơn hoặc bằng distance.
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
15/**
16Follow up: How to calculate distance from node to another node?
17 */
18function countPairs(root: TreeNode | null, distance: number): number {
19 if (root === null) {
20 return 0
21 }
22
23 let count_leaf = 0;
24 // Map: { distance_of_leaf_node: distance_of_leaf_node_to_current_parent_node }
25 const dfs = (node: TreeNode | null): Map<number, number> => {
26 if (node === null) {
27 return new Map();
28 }
29
30 if (node.left === null && node.right === null) {
31 const leaf_map = new Map<number, number>();
32 leaf_map.set(1, 1);
33 return leaf_map;
34 }
35
36 const left_distances = dfs(node.left)
37 const right_distances = dfs(node.right)
38
39 for (const [left_dist, left_count] of left_distances) {
40 for (const [right_dist, right_count] of right_distances) {
41 if (left_dist + right_dist <= distance) {
42 count_leaf += left_count * right_count;
43 }
44 }
45 }
46
47 let current_distance = new Map<number, number>();
48
49 for (const [left_dist, left_count] of left_distances) {
50 if (left_dist + 1 <= distance) {
51 current_distance.set(left_dist + 1, (current_distance.get(left_dist + 1) || 0) + left_count);
52 }
53 }
54
55 for (const [right_dist, right_count] of right_distances) {
56 if (right_dist + 1 <= distance) {
57 current_distance.set(right_dist + 1, (current_distance.get(right_dist + 1) || 0) + right_count);
58 }
59 }
60
61 return current_distance;
62 }
63
64 dfs(root);
65 return count_leaf
66};Khoảng cách node ở leaf của cây con: Khoảng cách node cha chung