-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0110.c
135 lines (122 loc) · 2.53 KB
/
q0110.c
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//
// q0110.c
// LeetCode
//
// Created by NowOrNever on 30/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0110.h"
#include "../common.h"
#include "q0104.h"
//110. Balanced Binary Tree
//Easy
//
//1520
//
//139
//
//Favorite
//
//Share
//Given a binary tree, determine if it is height-balanced.
//
//For this problem, a height-balanced binary tree is defined as:
//
//a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
//
//
//
//Example 1:
//
//Given the following tree [3,9,20,null,null,15,7]:
//
// 3
// / \
// 9 20
// / \
// 15 7
//Return true.
//
//Example 2:
//
//Given the following tree [1,2,2,3,3,null,null,4,4]:
//
// 1
// / \
// 2 2
// / \
// 3 3
// / \
// 4 4
//Return false.
//
//Accepted
//367,579
//Submissions
//875,998
//int maxDepth(struct TreeNode* root){
// if (root) {
// int left_len = maxDepth(root->left);
// int right_len = maxDepth(root->right);
// return 1 + (left_len > right_len ? left_len : right_len);
// }
// return 0;
//}
//
//bool isBalanced(struct TreeNode* root){
// if (root) {
// int diff = maxDepth(root->left) - maxDepth(root->right);
// if (diff > -2 && diff < 2) {
// return isBalanced(root->left) + isBalanced(root->right) == 2;
// }else{
// return 0;
// }
// }
// return 1;
//}
//bottom to up solution:
int q110depth(struct TreeNode* node){
if (!node) {
return 0;
}
int left_len = q110depth(node->left);
if (left_len == -1) {
return -1;
}
int right_len = q110depth(node->right);
if (right_len == -1) {
return -1;
}
if (abs(left_len - right_len) > 1) {
return -1;
}
return (left_len > right_len ? left_len : right_len) + 1;
}
bool isBalanced(struct TreeNode* root){
return (q110depth(root) != -1);
}
//int q110depth(struct TreeNode* root, bool *result){
// if (root) {
// int left = q110depth(root->left, result);
// int right = q110depth(root->right, result);
// *result = *result && abs(left - right) < 2;
// return (left > right ? left : right) + 1;
//// cost more time !??? why?
//// if (*result) {
//// return (left > right ? left : right) + 1;
//// }
//// return 0;
// }
// return 0;
//}
//
//bool isBalanced(struct TreeNode* root){
// bool result = true;
//
// q110depth(root, &result);
//
// return result;
//}
int question110(){
return 0;
}