Chúng ta hãy coi rằng chúng ta có nút gốc của cây nhị phân; nhiệm vụ là tìm và trả về tổng độ nghiêng của mọi nút.
Độ nghiêng của cây nhị phân không có gì khác ngoài việc xây dựng cây nhị phân bằng cách tìm sự khác biệt tuyệt đối của các nút con trong cây con bên trái và cây con bên phải ở mỗi cấp. Ở một số cấp độ cụ thể, các nút không có bất kỳ nút con nào, chúng tôi chỉ cần nghiêng bằng cách thay thế nút đó bằng số không.
Ví dụ
Đầu vào
Đầu ra:15
Giải thích: Tìm độ nghiêng ở mọi cấp của cây nhị phân đã cho,
Độ nghiêng của nút 3 =0
Độ nghiêng của nút 5 =0
Độ nghiêng của nút 7 =0
Độ nghiêng của nút 2 =abs (3-5) =2
Độ nghiêng của nút 9 =abs (0-7) =7
Độ nghiêng của nút 4 =abs ((3 + 5 + 2) - (9 + 7)) =6
Tổng độ nghiêng của tất cả các nút là =2 + 7 + 6 =15
Phương pháp tiếp cận để giải quyết vấn đề này
Cách tiếp cận đơn giản để giải quyết vấn đề cụ thể này là sử dụng truyền tải Tìm kiếm đầu tiên theo chiều rộng của bài đăng.
Trong khi duyệt qua cây nhị phân, chúng ta sẽ cố gắng tìm tổng tất cả các nút của cây con bên trái của nó và sau đó là cây con bên phải. Sau khi tổng được tìm thấy, chúng tôi sẽ tìm độ nghiêng của tất cả các nút bằng cách tính toán hiệu số tuyệt đối của tổng bên trái và tổng bên phải của các cây con.
- Lấy một cây nhị phân, cây này sẽ là đầu vào.
- Một hàm số nguyên sumNodes (nút cây *) lấy nút gốc của cây và trả về tổng của cây con bên trái và cây con bên phải.
- Một hàm số nguyên findTilt (treenode * root) lấy nút gốc làm tham số đầu vào và trả về tổng độ nghiêng của tất cả các nút.
Ví dụ
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int sumNodes(treenode * root, int & sum) {
if (root == NULL) return 0;
int lsum = sumNodes(root -> left, sum);
int rsum = sumNodes(root -> right, sum);
sum += abs(lsum - rsum);
return lsum + rsum + root -> data;
}
int findTilt(treenode * root) {
int sum = 0;
if (root == NULL) {
return 0;
}
sumNodes(root, sum);
return sum;
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(9);
root -> left -> right = createNode(5);
root -> left -> left = createNode(3);
root -> right -> right = createNode(7);
cout << findTilt(root) << endl;
return 0;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
15
Trong cây nhị phân đã cho, tổng độ nghiêng của tất cả các nút ở mọi cấp của cây là 15.