โปรแกรมตรวจสอบว่าต้นไม้เป็น Height Balanced หรือไม่ใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องตรวจสอบว่าความสูงของมันสมดุล (height balanced) หรือไม่ ต้นไม้สมดุลความสูงหมายถึง สำหรับทุกโหนด ความต่างสัมบูรณ์ของความสูงของซับทรีซ้ายและขวาต้องเป็น 0 หรือ 1

เช่น ต้นไม้ที่มีโครงสร้างดังภาพ ผลลัพธ์จะเป็น True

ขั้นตอนการแก้ปัญหา

• สร้างฟังก์ชัน dfs(node) ที่คืนค่าความสูงของซับทรี:
  • ถ้า node เป็น null: return 0
  • l = 1 + dfs(node->left)
  • r = 1 + dfs(node->right)
  • ถ้า |l - r| > 1: ตั้ง flag ret = false
  • return max(l, r)
• จาก main: ตั้ง ret = true, เรียก dfs(root), คืนค่า ret

ตัวอย่างโค้ด

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

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *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));
}

อินพุต

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

เอาต์พุต

1