[LeetCode/110/Java]Balanced Binary Tree
풀이
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return isBalanced(root, 1) > -1 ? true : false;
}
public int isBalanced(TreeNode root, int dept) {
if(dept == -1 || root == null) return dept;
if(root.left == null && root.right == null) return dept;
int left = dept;
int right = dept;
if(root.left != null) left = isBalanced(root.left, dept + 1);
if(root.right != null) right = isBalanced(root.right, dept + 1);
if(left + 1 < right || left > right + 1) return -1;
return left > right ? left : right;
}
}
후기
양쪽 노드의 깊이가 1이상 차이나지 않아야 되는 문제입니다.
처음에 문제 이해가 정말 안되서 살짝 헤맸네요
깊이우선방식(DFS)로 풀었지만 넓이우선방식(BFS)로 푸는게 더 좋았을 법 했네요
time complexity O(N)
space complexity O(N)
728x90
반응형
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode/112/Java]Path Sum (0) | 2022.06.05 |
---|---|
[LeetCode/111/Java]Minimum Depth of Binary Tree (0) | 2022.06.05 |
[LeetCode/104/Java]Maximum Depth of Binary Tree (0) | 2022.06.05 |
[LeetCode/101/Java]Symmetric Tree (0) | 2022.06.05 |
[LeetCode/100/Java]Same Tree (0) | 2022.06.05 |