[알고리즘] Leetcode_110_Balanced_Binary_Tree

Problem

Solve

• height-balanced 란, 왼쪽 오른쪽 subtree의 높이 차가 1이 초과하지 않는 이진 트리이다.
  
• 그렇다면 높이가 필요할 것이고, subtree의 높이차를 이용해 balance 여부를 확인할 수 있다.
• 높이를 구하는 문제는 104번으로 풀어보았었다.

	public int depth(TreeNode root) {    
        if(root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        
    }

• 높이차는 위의 depth 에서 높이를 리턴하는 함수 내에서 left subtree 와 right subtree 의 각각의 높이 차가 1 초과라면 정수 -1 을 반환한다.
• 최종적으로 depth 함수의 반환값이 -1이라면 unbalance 하기 때문에 false 를, -1이 아니라면 높이를 반환할 것이기 때문에 balance 하다는 의미이므로 true를 반환한다.

	int left = height(root.left);
    int right = height(root.right);
    
    if(left - right > 1 || right - left > 1) return -1;

• 다만, 이런 이진트리일 경우에는 현재 노드의 left와 right의 높이차만 비교하는 것이 아니라, left의 subtree나 right의 subtree들의 높이차를 비교한다.
  1 -> 2 -> 3-> 4-> 3 에서 높이는 총 2가 되고 다시 2로 돌아간다.
  2의 오른쪽 자식의 높이는 0이기 때문에 높이차가 1초과된 2가 되어 -1을 반환한다.
  
  
  
  
  
  

class Solution {
    public int height(TreeNode root){
        if(root == null) return 0;

        int left = height(root.left);
        if(left == -1) return -1;

        int right = height(root.right);
        if(right == -1) return -1;

        if(left - right > 1 || right - left > 1) return -1;

        return 1 + Math.max(left, right);

    
    }
    public boolean isBalanced(TreeNode root) {
        return height(root) == -1 ? false : true;
    }
}