2673. Make Costs of Paths Equal in a Binary Tree

Problem

Bạn có một perfect binary tree, mỗi node có một giá trị cost

💡

Perfect binary tree (cây nhị phân hoàn hảo) là một loại cây nhị phân mà:

Mỗi node bên trong (internal node) đều có chính xác hai node con

Tất cả các node lá (leaf node) đều nằm ở cùng một mức (level, hay độ sâu)

Lưu ý: Perfect binary tree là trường hợp đặc biệt của full binary tree (mọi node có 0 hoặc 2 con), nhưng thêm điều kiện là các nút lá phải ở cùng một mức

Perfect binary tree

typescripttypescript

1      1
2     / \
3    2   3
4   / \ / \
5  4  5 6  7

Full binary tree

typescripttypescript

Bạn có thể tăng cost của bất kỳ node nào bao nhiêu lần tùy thích (mỗi lần tăng 1)

Mục tiêu: Tổng cost trên mọi đường đi từ root đến leaf phải bằng nhau, với số lần tăng là ít nhất

Approach

Chiến lược giải

Bottom - up: Với mỗi node cha, ta muốn hai đường đi qua con trái và phải (từ cha đến leaf) có tổng cost bằng nhau

Với mỗi node, tính tổng cost lớn nhất từ node đó xuống lá qua hai con, và chênh lệch giữa hai nhánh sẽ là số lần tăng tối thiểu cần thiết tại node đó (cộng dồn vào đáp án)

Cập nhật cost của cha thành cost hiện tại cộng với cost lớn nhất của hai con (để khi lên cao hơn, nhánh nà cũng đã được cân bằng)

Cụ thể

Duyệt từ node cuối cùng của tầng áp chót lên root

Với mỗi node i, hai còn là L = 2*i + 1 và R = 2*i + 2 (theo mảng 0-indexes)

Tính ans += abs(cost[L] - cost[R])

Cập nhật cost[i] += max(cost[L], cost[R])

Solution

typescripttypescript

1function minIncrements(n: number, cost: number[]): number {
2    let ans = 0;
3    for(let i = Math.floor(n / 2) - 1;i >=0;--i) {
4	    const L = i * 2 + 1;
5	    const R = i * 2 + 2;
6	    ans += Math.abs(cost[L] - cost[R]);
7	    cost[i] += Math.max(cost[L], cost[R]);
8    }
9    return ans
10};

Loading content...

1function minIncrements(n: number, cost: number[]): number { 2 let ans = 0; 3 for(let i = Math.floor(n / 2) - 1;i >=0;--i) { 4 const L = i * 2 + 1; 5 const R = i * 2 + 2; 6 ans += Math.abs(cost[L] - cost[R]); 7 cost[i] += Math.max(cost[L], cost[R]); 8 } 9 return ans 10};

2673. Make Costs of Paths Equal in a Binary Tree

Related Posts

Related Posts

2673. Make Costs of Paths Equal in a Binary Tree

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists