110 平衡二叉树

题目

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

解题思路

https://leetcode-cn.com/problems/balanced-binary-tree/solution/balanced-binary-tree-di-gui-fang-fa-by-jin40789108/

自底向上遍历每个节点，按照先序遍历的方式，遍历到最下一层（第h层）叶子节点高度为0，该叶子节点的父节点（第h-1层）高度为1，再往上一层，则第h-1层左子树高度为1，用相同方式计算右子树高度，根据h-1层左右子树的高度，判断该子树是不是平衡二叉树，如果不是，则“剪枝”，直接向上返回结果，否则，选取左右子树最大高度+1作为第h-2层父节点的高度。

递归设计

子问题：自底向上，依次计算每个子树的左右子树高度差，同时记录该子树的最大高度

递归函数需要完成的任务：

计算左右子树高度差：高度差<2，返回左右子树最大高度+1；高度差>=2，返回-1；

临界情况：

1 子树为空，返回高度为0

2 定义高度为-1代表该子树不平衡，直接返回高度-1

调用情况：选取节点之后，对左右子树进行递归调用，分别获取左右子树高度，从而判断以该节点为根节点的子树是否满足平衡二叉树的条件。

/**
 * 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) {
        return recur(root)!=-1;
    }
    private int recur(TreeNode root){
        if(root==null) return 0;
        int left = recur(root.left);
        if(left==-1) return -1;
        int right = recur(root.right);
        if(right==-1) return -1;
        if(Math.abs(left-right)>=2) return -1;
        return Math.max(left,right)+1;
    }
}