โปรแกรมตรวจสอบต้นไม้สูงสมดุลหรือไม่ในภาษา C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องตรวจสอบความสูงของมันว่าสมดุลหรือไม่ เรารู้ว่าสำหรับต้นไม้ที่มีความสูงสมดุล สำหรับทุกโหนดในต้นไม้ ความแตกต่างแน่นอนของความสูงของต้นไม้ย่อยด้านซ้ายและความสูงของต้นไม้ย่อยด้านขวาคือ 0 หรือ 1

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด
ถ้าโหนดเป็นโมฆะ −
- คืนค่า 0
l :=1 + dfs(ซ้ายของโหนด)
r :=1 + dfs(ทางขวาของโหนด)
ถ้า |l - r|> 1 แล้ว −
- ret :=เท็จ
คืนค่าสูงสุดของ l และ r
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
ret :=จริง
dfs(root)
รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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