320x100
https://leetcode.com/problems/balanced-binary-tree/
Balanced Binary Tree - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
이진 트리가 주어졌을 때, 균형 트리(왼쪽 서브트리와 오른쪽 서브트리의 높이가 2이상 차이나지 않는 트리)를 만족하는지 확인하는 문제다.
간단히 생각했을 때는 양측 최대 깊이를 구해서 루트에서 비교했더니 아래와 같은 조건에서 문제가 됐다.
매 노드마다 검사를 진행해서 결과를 도출해낸다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int calculDepth(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int left = calculDepth(node->left);
int right = calculDepth(node->right);
if (abs(left - right) > 1 || left == -1 || right == -1) {
return -1;
}
return 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
if (calculDepth(root) == -1) {
return false;
}
else {
return true;
}
}
};
320x100
'코딩테스트 준비 > leetcode' 카테고리의 다른 글
1302. Deepest Leaves Sum [Medium] (0) | 2021.07.21 |
---|---|
144. Binary Tree Preorder Traversal [Easy] (0) | 2021.07.21 |
543. Diameter of Binary Tree [Easy] (0) | 2021.07.20 |
94. Binary Tree Inorder Traversal (0) | 2021.07.19 |
108. Convert Sorted Array to Binary Search Tree (0) | 2021.07.18 |