एक बाइनरी ट्री ऊंचाई-संतुलित (height-balanced) होता है यदि प्रत्येक नोड के लिए उसके बाएं और दाएं सबट्री की ऊंचाई का निरपेक्ष अंतर 0 या 1 हो।
दिए गए ट्री के लिए आउटपुट true (1) है।
समाधान दृष्टिकोण (पोस्ट-ऑर्डर DFS)
- एक ग्लोबल फ्लैग
ret = trueरखें। dfs(node)फंक्शन नोड की ऊंचाई वापस करता है:- यदि नोड नल, तो 0 वापस करें।
- बाएं और दाएं सबट्री की ऊंचाई पाएं:
l = 1 + dfs(left),r = 1 + dfs(right)। - यदि
|l - r| > 1, तोret = falseसेट करें। max(l, r)वापस करें।
- मुख्य फंक्शन
dfs(root)कॉल करता है औरretवापस करता है।
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;
}
इनपुट
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