[leetcode] 110. Balanced Binary Tree

 

https://leetcode.com/problems/balanced-binary-tree

 

 

주어진 Binary Tree 가 균형잡힌 것인지 아닌지 확인하면 된다.

재귀 함수를 사용하여 depth 를 누적한 후, 차이가 1보다 크다면 False 를 반환한다.

depth 차이 계산을 root 에서만 하게 되면, 아래와 같이 양측의 depth 가 같은 경우에 True 를 반환하게 된다.

 

따라서 재귀 함수를 실행 할 때마다 차이를 확인해야 한다.

균형잡히지 않았다는 것이 확인되면, 5001 이라는 숫자를 반환하는데 이는 '이미 균형잡히지 않았다'는 의미이다.

isBalanced 에서 5001보다 큰지 확인하여, 크다면 False 를 반환하는 로직을 추가한다.

 

 

class Solution:
    def func(self, tree: Optional[TreeNode]) -> int:
        if(not tree): return 0
        left = self.func(tree.left)
        right = self.func(tree.right)
        if(abs(left-right)>1): return 5001
        return max(left, right) + 1
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if(not root or (not root.left and not root.right)): return True
        left = self.func(root.left)
        right = self.func(root.right)
        if(left>5000 or right>5000): return False
        else: return abs(left - right) <= 1

 

 

 

---

 

 

 

< English (feedback by ChatGPT) >

 

The task is to check whether the given Binary Tree is balanced or not.

(The task is to check whether the given binary tree is balanced.)

 

Accumulate the depth using a recursive function and return False when the difference between two depths is more than 1.

(We use a recursive function to calculate and accumulate the depth of each subtree.

If the difference in depth between the left and right subtrees is greater than 1, we return False.)

 

If we check the depth difference at the root, it will return True when the both child's depth are the same.

(If we only check the depth difference at the root, the function may incorrectly return True in cases where both child depths are equal, even if there’s an imbalance deeper in the tree.)

 

So we should check the difference everytime when the recursive function runs.

(Therefore, we need to check the depth difference at every step during the recursive calls.)

If we check it is unbalanced, return 5001 number which means 'it is unbalanced'.

(When an imbalance is detected, we return a special value like 5001 to indicate the tree is already unbalanced.)

 

We check the difference is more than 5001 at isBalanced, and if so, add a logic to return False.
(In the isBalanced function, we check whether the returned depth is greater than 5000; if so, we return False.)