[leetcode]Balanced Binary Tree

1751 단어 LeetCode
새 블 로그 주소: [leetcode]Balanced Binary Tree
 
http://oj.leetcode.com/problems/balanced-binary-tree/
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
 밸 런 스 트 리 인지 아 닌 지 판단 하기
백과 
AVL 트 리 (AVL 알고리즘 과 달리) 라 고도 부 르 며 다음 과 같은 성질 을 가지 고 있 습 니 다. 빈 나무 나 좌우 두 나무의 높이 차 이 는 절대 1 을 초과 하지 않 고 좌우 두 개의 나 무 는 모두 균형 이 잡 힌 이 진 트 리 입 니 다.
 게 으 름 피 우 는 데 재 귀 알고리즘 을 써 서 난이도 가 별로 없다.
    public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		int left = getHeight(root.left);
		int right = getHeight(root.right);
		if (Math.abs(left - right) > 1) {
			return false;
		}
		if (root.left != null && !isBalanced(root.left)) {
			return false;
		}
		if (root.right != null && !isBalanced(root.right)) {
			return false;
		}
		return true;
    }
	  private int getHeight(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return 1;
		}
		int leftHeight = getHeight(root.left);
		int rightHeight = getHeight(root.right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

 

좋은 웹페이지 즐겨찾기