Java clear solution.


  • 2
    J
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
       // 求树的深度
    	public static int depth(TreeNode root) {
    		if (root.left == null && root.right == null)
    			return 1;
    		else if (root.left != null && root.right == null)
    			return 1 + depth(root.left);
    		else if (root.left == null && root.right != null)
    			return 1 + depth(root.right);
    		else {
    			int num1 = 1 + depth(root.left);
    			int num2 = 1 + depth(root.right);
    			return num1 > num2 ? num1 : num2;
    		}
    	}
    
    	// 判断是不是AVL树
    
    	// 基本思路:
    	//
    	// 平衡二叉树的定义是:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
    	//
    	// 先计算每个节点左右子树的高度差,一旦有某个节点的左右子树高度差的绝对值大于一则表明这不是一颗平衡树。
    	public static boolean isBalanced(TreeNode root) {
    		if (root == null)
    			return true;
    		return yesOrNo(root) && isBalanced(root.left) && isBalanced(root.right);
    	}
    
    	/**
    	 * @param root
    	 * @return
    	 */
    	private static boolean yesOrNo(TreeNode root) {
    		if (root == null)
    			return true;
    		int left = 0, right = 0;
    		if (root.left != null)
    			left = depth(root.left);
    		if (root.right != null)
    			right = depth(root.right);
    		if (Math.abs(left - right) <= 1)
    			return true;
    		else
    			return false;
    	}
    	   
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.