-
Notifications
You must be signed in to change notification settings - Fork 0
/
IsBalanced.cpp
73 lines (59 loc) · 1.78 KB
/
IsBalanced.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//
// Created by Wanhui on 3/22/20.
//
#include <algorithm>
#include "IsBalanced.h"
bool Solution55_2::isBalanced(BiTreeNode *root) {
if (root == nullptr) {
return true;
}
// 递归左子树
int leftDepth = maxDepth(root->left);
// 递归右子树
int rightDepth = maxDepth(root->right);
// 左右子树深度差
int diff = leftDepth - rightDepth;
// 如果大于1则不平衡
if (diff > 1 || diff < -1) {
return false;
}
// 对左右子树进行递归判断
return isBalanced(root->left) && isBalanced(root->right);
}
int Solution55_2::maxDepth(BiTreeNode *root) {
if (root == nullptr) {
return 0;
}
// 递归左子树
int leftDepth = maxDepth(root->left);
// 递归右子树
int rightDepth = maxDepth(root->right);
// 返回左右子树深度较大的值加1
return std::max(leftDepth, rightDepth) + 1;
}
bool Solution55_2::isBalanced2(BiTreeNode *root) {
int depth = 0;
return balance(root, depth);
}
bool Solution55_2::balance(BiTreeNode *root, int &depth) {
// 叶节点是平衡的,且深度为0
if (root == nullptr) {
depth = 0;
return true;
}
// 定义左右子树的深度
// 定义左右子树的深度差
int left = 0, right = 0, diff = 0;
// 如果该节点的左右子树是平衡的
if (balance(root->left, left) && balance(root->right, right)) {
// 则当前节点的左右子树根据返回的深度计算差
diff = left - right;
// 如果深度差小于1则是平衡的
if (diff <= 1 && diff >= -1) {
// 同时当前节点的深度为左右子树深度较大值加1
depth = 1 + (left > right ? left : right);
return true;
}
}
return false;
}