Chương trình kiểm tra cây nhị phân có cân bằng chiều cao hay không trong C++

Cho một cây nhị phân. Kiểm tra xem cây có cân bằng chiều cao (height-balanced) hay không. Cây cân bằng nếu tại mọi nút, chênh lệch tuyệt đối chiều cao cây con trái và phải ≤ 1.

Ví dụ: cây gốc 25, trái 19, phải 4, ... → True (1).

Thuật toán (DFS post-order)

• Hàm dfs(node) trả về chiều cao của cây con gốc tại node.
• Nếu node == NULL: trả về 0.
• Đệ quy tính l = 1 + dfs(left), r = 1 + dfs(right).
• Nếu |l - r| > 1: đánh dấu ret = false.
• Trả về max(l, r).
• Gọi dfs(root), trả về ret.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool ret;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int l = 1 + dfs(node->left);
        int r = 1 + dfs(node->right);
        if (abs(l - r) > 1) ret = false;
        return max(l, r);
    }
    bool isBalanced(TreeNode* root) {
        ret = true;
        dfs(root);
        return ret;
    }
};

int main() {
    Solution ob;
    TreeNode *root = new TreeNode(25);
    root->left = new TreeNode(19);
    root->right = new TreeNode(4);
    root->left->left = new TreeNode(9);
    root->left->right = new TreeNode(7);
    cout << ob.isBalanced(root);
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(25); root->left = new TreeNode(19); root->right = new TreeNode(4); root->left->left = new TreeNode(9); root->left->right = new TreeNode(7);

Đầu ra

1