Giả sử chúng ta có một cây nhị phân; chúng ta phải kiểm tra xem chiều cao của nó có cân đối hay không. Chúng ta biết rằng đối với cây cân bằng chiều cao, đối với mọi nút trong cây, hiệu số tuyệt đối của chiều cao của cây con bên trái và chiều cao của cây con bên phải là 0 hoặc 1.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là True
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm dfs (), hàm này sẽ sử dụng nút,
-
nếu nút là null, thì -
-
trả về 0
-
-
l:=1 + dfs (bên trái của nút)
-
r:=1 + dfs (bên phải của nút)
-
nếu | l - r |> 1, sau đó -
-
ret:=false
-
-
trả về tối đa l và r
-
Từ phương thức chính, hãy làm như sau -
-
ret:=true
-
dfs (gốc)
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầ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