leetcode 110. Balanced Binary Tree-밸런스 두 갈래 나무 | 깊이

757 단어 LeetCode
원제 링크: 110.Balanced Binary Tree
[생각]
이 문제는 귀속수의 깊이가 두루 흐르는 응용이다.제목의 뜻에 따라 한 노드에 대해 각 노드의 왼쪽, 오른쪽 나무의 깊이를 계산하고 왼쪽, 오른쪽 나무의 깊이가 1보다 크면 이 나무는 비균형적일 수 있다.그러면 각 노드에 귀속되고 어떤 노드가 비균형을 발견하면false로 돌아가고, 모든 노드가 균형을 이루면true로 돌아간다.
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int getDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
    }

226/226
 test cases passed. Runtime: 2 ms  Your runtime beats 22.68% of javasubmissions.

좋은 웹페이지 즐겨찾기