Độ nghiêng cây nhị phân (Binary Tree Tilt) trong C++

Tilt của node = |tổng subtree trái - tổng subtree phải|. Tilt của cây = tổng tilt tất cả node.

Ví dụ

Output: 15

Tilt node 3,5,7 = 0 (lá)

Tilt node 2 = |3-5| = 2

Tilt node 9 = |0-7| = 7

Tilt node 4 = |(3+5+2) - (9+7)| = 6

Tổng = 2+7+6 = 15

Cách tiếp cận: Post-order DFS

• Hàm sumNodes(node, &sum) trả về tổng subtree, cập nhật sum tilt
• Đệ quy left, right → lsum, rsum
• sum += abs(lsum - rsum)
• Trả về lsum + rsum + node->data

Code C++

#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) 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) 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;
}

Kết quả

15