leetcode刷题：二叉树11（平衡二叉树）

110.平衡二叉树

力扣题目链接

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

这题，，，，好难，对我来说。
答案好巧妙。
使用递归
相当于层层往上返回，当都是叶子结点时，树的高度为0 + 1 ，否则就比较树的左右子树高度，如果差值 > 1，则是非平衡二叉树，不然取左右子树最高树 + 根结点 高度 为当前树的高度。

package com.programmercarl.tree;

import com.programmercarl.util.GenerateTreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/** * @ClassName IsBalanced * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 11:21 * @Version 1.0 * https://leetcode.cn/problems/balanced-binary-tree/ * 110. 平衡二叉树 **/
public class IsBalanced {
    
    /** * 递归三部曲 * 1. 明确递归函数的参数和返回值 * 参数：当前传入节点 * 返回值：以当前传入结点为根结点的树的高度 * 如果当前传入结点为根结点的二叉树不是平衡二叉树，返回 -1 * <p> * 2. 明确终止条件 * 遇到空节点终止，返回0，表示当前结点以此结点为根结点的树的高度为0 * <p> * 3. 明确单层递归的逻辑 * 如何判断左右子树不平衡？ * 左右子树高度差 > 1 返回 -1 * 返回当前高度差 * * @param root * @return */
    public boolean isBalanced(TreeNode root) {
    
        return getHeight(root) != -1;
    }

    // 高度为-1则不是平衡二叉树
    public int getHeight(TreeNode root) {
    
        //空结点高度为0
        if (root == null) {
    
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
    
            return - 1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
    
            return -1;
        }
        //高度差 > 1 , 则不对称
        if (Math.abs(leftHeight - rightHeight) > 1) {
    
            return -1;
        }
        //如果左右子树为平衡二叉树，返回树的整体高度 + 1
        // 整体高度为 当前最高子树的高度 + 根结点的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
}