मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जांचना है कि इसकी ऊंचाई संतुलित है या नहीं। हम जानते हैं कि एक संतुलित ऊंचाई वाले पेड़ के लिए, पेड़ में प्रत्येक नोड के लिए, इसके बाएं उपट्री की ऊंचाई और इसके दाएं उपट्री की ऊंचाई का पूर्ण अंतर 0 या 1 है।
तो, अगर इनपुट पसंद है
तो आउटपुट सही होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें dfs(), यह नोड लेगा,
-
यदि नोड शून्य है, तो -
-
वापसी 0
-
-
l :=1 + dfs (नोड के बाएँ)
-
r :=1 + dfs (नोड के दाएं)
-
अगर |एल - आर|> 1, फिर -
-
रिट :=असत्य
-
-
एल और आर की अधिकतम वापसी
-
मुख्य विधि से निम्न कार्य करें -
-
रेट :=सच
-
dfs(रूट)
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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);
आउटपुट
1