資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式檢查樹是否為平衡樹
假設我們有一個二叉樹，我們需要檢查其高度是否平衡。我們知道，對於一個高度平衡的樹，樹中每個節點的左子樹高度和右子樹高度的絕對差為 0 或 1。
所以，如果輸入如下所示：
則輸出為 True
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 dfs()，它將接收節點作為引數。
如果節點為空，則：
返回 0
l := 1 + dfs(節點的左子節點)
r := 1 + dfs(節點的右子節點)
如果 |l - r| > 1，則：
ret := false
返回 l 和 r 中的最大值
在主方法中執行以下操作：
ret := true
dfs(根節點)
返回 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;
}
};
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
更新於: 2020年10月8日
501 次瀏覽
廣告