T38，数的递归

描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：n≤100n≤100,树上节点的val值满足 0≤n≤10000≤n≤1000

要求：空间复杂度O(1)O(1)，时间复杂度 O(n)O(n)

输入描述：

输入一棵二叉树的根节点

返回值描述：

输出一个布尔类型的值

示例1

输入：

{1,2,3,4,5,6,7}

返回值：

true

示例2

输入：

{}

返回值：

true

递归实现：

public class Solution {public int deep(TreeNode root){if(root==null){return 0;}int left=deep(root.left);int right=deep(root.right);if(left>right){return left+1;}else{return right+1;}}public boolean IsBalanced_Solution(TreeNode root) {if(root==null){return true;}int left=deep(root.left);int right=deep(root.right);if(left-right>1||right-left>1){return false;}return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);}
}

思路：

一个求左右子树深度的方法deep，deep方法可递归调用deep方法，再次调用的参数为传入节点的左右子树，最后返回左右节点的值。结束标志是左右子树为空，返回0；

从根节点开始，调用deep方法，判断左右子树深度之差。递归调用该方法，参数为左右子树节点。结束标志是左右子树为0；

 自底向上：

 实现代码：

public class Solution {public boolean IsBalanced_Solution(TreeNode root) {//空树也是平衡二叉树if(root == null)return true;return getdepth(root) != -1;}public int getdepth(TreeNode root) {if(root == null)return 0;//递归计算当前root左右子树的深度差int left = getdepth(root.left);//当前节点左子树不平衡，则该树不平衡if(left < 0) return -1;int right = getdepth(root.right);//当前节点右子树不平衡，则该树不平衡if(right < 0) return -1;//计算深度差return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);}
}

 时间复杂度：O（N）

空间复杂度：O（N）

附录：Math函数的方法Math的几个方法Math.round()、Math.ceil()、Math.floor()和Math.abs()记录一下_MingFlying的博客-CSDN博客