[leetcode] Balanced Binary Tree

유의할점

bottom up 보기

풀이

정의대로 풀었다.

균형잡힌 트리란 , 왼쪽 자식 트리 높이와 오른쪽 자식 트리 높이 차이가 1을 넘지 않는것이다. 또한 왼쪽 자식 트리와 오른쪽 자식 또한 균형잡힌 트리여야한다.

내 코드는 모든 노드들에 대해 균형잡힌 트리인지 판단한다. O(N)

각 노드에서 균형잡힌 트리를 판단할때 왼쪽과 오른쪽 높이를 구한다. O(N)

따라서 최종 시간 복잡도는 O(N^2)이된다.

DFS 이용, 높이를 구하면서 균형잡힌 트리인지 판단하는 방법을 사용하면 O(N)에 구할수있다. (Bottom-up)

코드

C++ : 내가 짠 코드 O(N^2)

/**
 * 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 int height(TreeNode root){
        if(root==null)
            return 0;
        return 1 + Math.max(height(root.left),height(root.right));
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        int dif = leftHeight - rightHeight;
        return Math.abs(leftHeight-rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
}

JAVA : bottom up O(N)

class solution {
public:
int dfsHeight (TreeNode *root) {
        if (root == NULL) return 0;
        
        int leftHeight = dfsHeight (root -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight (root -> right);
        if (rightHeight == -1) return -1;
        
        if (abs(leftHeight - rightHeight) > 1)  return -1;
        return max (leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode *root) {
        return dfsHeight (root) != -1;
    }
};