平衡二叉树

题目

image.png

image.png

实现

1、首先需要计算节点的高度，当前节点高度=max(左子树,右子树)+1。
2、判断是否平衡，若abs(左子树高度-右子树高度)>1，则不平衡。
3、若当前节点平衡，则递归判断左子树是否平衡和右子树是否平衡。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root != null && (Math.abs(high(root.left) - high(root.right)) > 1 || !isBalanced(root.left) || !isBalanced(root.right))) {
            return false;
        }
        return true;
    }
    
    public int high(TreeNode t) {
        if(t == null) {
            return 0;
        }
        return Math.max(high(t.left),high(t.right)) + 1;
    }
}

提交

image.png