判断是不是平衡二叉树
题目描述
示例
代码
代码1 深度优先遍历，获取每一层的高度，过程中比较左子树右子树的高度差
js
/*
题目要求不用考虑是否是排序的二叉树，只考虑平衡性
平衡二叉树：左子树与右子树的高度差绝对值小于等于1，同时左子树与右子树都是平衡二叉树。
其实与求二叉树的深度是一样的，只不过是在求得过程中比较左子树与右子树的高度差绝对值是否<1
*/
function IsBalanced_Solution(pRoot)
{
let isBalanced = true // 默认是平衡二叉树 true
// 判断，在递归的途中判断左子树和右子树的高度差是否相差1以内，大于1就更改 isBalanced 为false
dfs(pRoot)
return isBalanced // 返回结果
// 深度遍历，获取每一层的高度
function dfs(root){
// 出口
if(!root) return 0 // null的高度默认为0
let lval = dfs(root.left)
let rval = dfs(root.right)
if(Math.abs(lval - rval) > 1){
isBalanced = false
}
return Math.max(lval, rval) + 1
}
}时间复杂度：O(N)。N为树的节点个数。最差情况下需要遍历所有节点。
空间复杂度：O(N)。若树退化成了链表，则递归深度为节点的个数，需要用到O(N)的栈空间。
代码2 优化代码1，如果在某次判断得出已经不属于平衡二叉树了，让递归提前返回，无需再继续比较其它节点
js
/*
题目要求不用考虑是否是排序的二叉树，只考虑平衡性
平衡二叉树：左子树与右子树的高度差绝对值小于等于1，同时左子树与右子树都是平衡二叉树。
其实与求二叉树的深度是一样的，只不过是在求得过程中比较左子树与右子树的高度差绝对值是否<1
*/
function IsBalanced_Solution(pRoot)
{
let isBalanced = true // 默认为true
// 判断
dfs(pRoot)
return isBalanced
// 深度遍历，获取每一层的高度
function dfs(root){
// 出口
if(!root) return 0 // null的高度默认为0
let lval = dfs(root.left)
if(lval === -1) return -1 // 提前返回
let rval = dfs(root.right)
if(rval === -1) return -1 // 提前返回
if(Math.abs(lval - rval) > 1){
isBalanced = false // // 不是平衡树
// 优化，增加标识 -1 ，已经不满足了，提前返回结果
return -1
}
return Math.max(lval, rval) + 1
}
}时间复杂度：O(N)。N为树的节点个数。最差情况下需要遍历所有节点。
空间复杂度：O(N)。若树退化成了链表，则递归深度为节点的个数，需要用到O(N)的栈空间。