balanced-binary-tree

/**
*
* @author gentleKay
* 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.
*
* 给定一个二叉树,确定它是否是高度平衡的。
* 对于这个问题,高度平衡二叉树被定义为一个二叉树,其中每个节点的两个子树的深度相差不超过1。
*
*/

在解决这道题目之前,我们必须要知道如何求一个二叉树的深度?

public int getDepth(TreeNode root) {
		if (root == null ) {
			return 0;
		}
		int left = getDepth(root.left)+1;   //每迭代一次,深度就+1
int right = getDepth(root.right)+1; return left > right ? left : right ; }

  我们再来分析一下题目,自从我们知道了 如何求一个二叉树的深度之后,这道题就比较简单了。

/**
 * 
 * @author gentleKay
 * 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.
 * 
 * 给定一个二叉树,确定它是否是高度平衡的。
 * 对于这个问题,高度平衡二叉树被定义为一个二叉树,其中每个节点的两个子树的深度相差不超过1。
 * 
 */

public class Main19 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		
		
//		root.right = new TreeNode(3);
//		root.right.left = new TreeNode(6);
//		root.right.right = new TreeNode(7);
		System.out.println(Main19.isBalanced(root));
	}
	
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
	 
	public static boolean isBalanced(TreeNode root) {
		
		if (root == null) {
			return true;
		}
		
		int left = getDepth(root.left); //拿到 相当于根节点的左右两个节点的深度
		int right = getDepth(root.right);
		if (Math.abs(left-right) > 1) { //并比较不超过 1 ,超过了 返回 false。
			return false;
		}
        return isBalanced(root.left) && isBalanced(root.right); // 在进行迭代,根节点的左右节点的左右节点进行分析深度与否。
    }
	
	public static int getDepth(TreeNode root) {
		if (root == null ) {
			return 0;
		}
		int left = getDepth(root.left)+1;
		int right = getDepth(root.right)+1;
		return left > right ? left : right ;
	}

}

  

上一篇:555 div3 F. Maximum Balanced Circle*


下一篇:LeetCode开心刷题五十二天——110. Balanced Binary Tree