-
Notifications
You must be signed in to change notification settings - Fork 0
/
balanced-binary-tree.h
30 lines (21 loc) · 779 Bytes
/
balanced-binary-tree.h
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
#ifndef BALANCED_BINARY_TREE_H_
#define BALANCED_BINARY_TREE_H_
#include <algorithm>
#include "tree-node.h"
namespace solution {
bool isBalanced(TreeNode* root) {
// Brute force
// Runtime: 16 ms, faster than 20.87% of C++ online submissions for Balanced Binary Tree.
// Memory Usage: 20.9 MB, less than 74.77% of C++ online submissions for Balanced Binary Tree.
//
if (root == nullptr) return true;
if (root->left == nullptr && root->right == nullptr) return true;
return std::abs(depth(root->left) - depth(root->right)) < 2;
}
int depth(TreeNode* node) {
if (node == nullptr) return 0;
if (node->left == nullptr && node->right == nullptr) return 1;
return std::max(depth(node->left), depth(node->right)) + 1;
}
}
#endif // BALANCED_BINARY_TREE_H_