剑指 Offer 55 - II. 平衡二叉树

image.png

解题思路

首先明白平衡二叉树的树的高度是如何计算的
Math.max(l,r)+1//左子树和右子树的最大高度+1
通过比较左右子树的高度差来判断是否为平衡树

image.png

代码

/**
 * 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) {
        int a=dfs(root);
        if(a==-1) return false;
         return true;
    }
    public int dfs(TreeNode root){
        if(root==null) return 0;
        int l=dfs(root.left);
        if(l==-1) return -1;//如果左子树不平衡，直接跳出，不用判断右子树，直接返回-1
        int r=dfs(root.right);
        if(r==-1) return -1;
        return Math.abs(l-r)<2? Math.max(l,r)+1:-1;//左子树和右子树的高度差大于1，就标记为-1，-1仅仅是一个标记，
//换成其他数字也可以
            }
}