Balanced Binary Tree - LeetCode

Problem

1. input: 이진트리의 루트 노드 root
2. output: 주어진 트리가 height-balanced인지 리턴
   • The number of nodes in the tree is in the range [0, 5000].
   • -10^4 <= Node.val <= 10^4

Idea

트리가 height-balanced 가 되려면 어떤 노드를 기준으로하든, 좌,우 자식을 시작으로 하는 서브트리의 depth 차이가 1이하여야 한다. 즉, 리프노드부터 거꾸로 올라오며 좌,우 서브트리의 depth를 비교하면 된다.

루트노드부터 DFS탐색 후, 리턴 값을 통해 depth를 비교하면 된다. 하지만 여기서 주의할 점은

‘이미 하위 서브트리에서 height-balanced가 아닌 경우, 상위 노드의 좌,우 서브트리의 depth차이와 상관 없이 항상 false’

라는 것이다. 따라서 리턴값을 depth뿐만 아니라 해당 노드까지 height-balaced한지 Boolean도 리턴하여야 한다 → Sol1

Solution

1. DFS

   리턴 값 ⇒ Pair(해당 노드까지 height-balaced한지, 해당 노드를 시작으로 하는 서브트리의 depth)

   /**
    * Example:
    * var ti = TreeNode(5)
    * var v = ti.`val`
    * Definition for a binary tree node.
    * class TreeNode(var `val`: Int) {
    *     var left: TreeNode? = null
    *     var right: TreeNode? = null
    * }
    */
   class Solution {
       fun isBalanced(root: TreeNode?): Boolean {
          return recSearch(root).first
       }
   
       fun recSearch(root: TreeNode?): Pair<Boolean, Int> {
           if (root == null) return Pair(true, 0)
           val left = recSearch(root!!.left) // 왼쪽 자식 DFS
           if (!left.first) return Pair(false, 0) // 왼쪽자식 이미 height-balanced X
           val right = recSearch(root!!.right) // 오른쪽 자식 DFS
           if (!right.first) return Pair(false, 0) // 오른쪽자식 이미 height-balanced X
           val depth = maxOf(left.second, right.second) + 1 // 좌,우 최대 depth + 자기자신
           return Pair((Math.abs(left.second - right.second) <= 1 && left.first && right.first), depth)
       }
   }
   

   시간 복잡도: 트리 탐색 = n

   

Point