每日一练：LeeCode-110、平衡二叉树【二叉树】

本文是力扣LeeCode-110、平衡二叉树 学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

整体思路

求深度可以从上到下去查 所以需要前序遍历（中左右），??度只能从下到上去查，所以只能后序遍历（左右中）

这道题既然要求?较?度，必然是要后序遍历

代码思路：

1.平衡二叉树任意节点两边的子树深度相差绝对值不会超过1，且每个子树都满足这个条件，
   那我们可以对每个节点找到两边的深度。
2.再判断是否两边相差绝对值超过1。
3.然后因为每个子树都满足这个条件，我们还需要遍历二叉树每个节点当成一棵子树进行判
  断，而对于每个每个节点判断后，其子节点就是子问题，因此可以用递归。

步骤：

1.IsBalanced_Solution递归遍历二叉树所有节点。
2.对于每个节点判断，调用depth()函数获取子树深度。
3.depth()函数递归获取子树深度，只需要不断往子节点深度遍历，累加左右深度的较大值。
4.根据深度判断该节点下的左右子树是否为平衡二叉树。
5.每个节点层层进行判断高度。

递归法

1、明确递归函数的参数和返回值

int depth(TreeNode node)

2、明确终?条件

//空树为平衡二叉树,无论是根节点，还是叶子结点的子节点都可以判断
if(root==null)return true;

3.、明确单层递归的逻辑

int left = depth(root.left);	 // 左
int right = depth(root.right);	 // 右
//左子树深度减去右子树相差绝对值大于1
if(Math.abs(left-right)>1)return false;	// 中
//同时，左右子树还必须是平衡的，只要遇到null，都会为true，
//有一个为false，都为false了
return isBalanced(root.left)&&isBalanced(root.right);

depth函数用于求传入节点为根节点这个子数的高度

//计算该子树深度函数
int depth(TreeNode node){
    if(node==null)return 0;
    int left = depth(node.left);
    int right = depth(node.right);
    return left>right?left+1:right+1;	// 以当前节点为根节点的树的最??度
}

整体代码

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;
        int left = depth(root.left);
        int right = depth(root.right);
        if(Math.abs(left-right)>1)return false;
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    int depth(TreeNode node){
        if(node==null)return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        return left>right?left+1:right+1;
    }
}