【js刷题--树】JZ79 判断是不是平衡二叉树

描述
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree）
具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

基本思想首先要写一个函数，获取树的高度；当根节点不为空时，则可以让左右子树的绝对值小于1，同时，保证左右子树都是平衡二叉树。

/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function IsBalanced_Solution(pRoot)
{
// write code here
if(!pRoot) return true
return (Math.abs(getMaxDepth(pRoot.right)-getMaxDepth(pRoot.left))<=1&&IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right))
}
function getMaxDepth(root){
if(!root) return 0
return Math.max(getMaxDepth(root.right)+1,getMaxDepth(root.left)+1)
}
module.exports = {
IsBalanced_Solution : IsBalanced_Solution
};

/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
// 求二叉树的深度
function depth(root){
if(!root)
return 0
// 左树深度
var l=depth(root.left);
// 右树深度
var r=depth(root.right);
return Math.max(l,r)+1;
}
function IsBalanced_Solution(pRoot)
{
// write code here
// 先处理特殊情况，如果是一颗空树，则是平衡二叉树
if(!pRoot)
return true;
// 左右树的差距
let gap=Math.abs(depth(pRoot.left)-depth(pRoot.right));
// 只有当，树中任意一个节点为根节点的左右树高度差小于1，才能确定是平衡树
if(gap<=1)
return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
// 如果左右两树的差距大于1，则可肯定，不是平衡树
else
return false;
}
module.exports = {
IsBalanced_Solution : IsBalanced_Solution
};

最后

以上就是老迟到鞋子为你收集整理的【js刷题--树】JZ79 判断是不是平衡二叉树的全部内容，希望文章能够帮你解决【js刷题--树】JZ79 判断是不是平衡二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。