大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说自平衡二叉查找树_二叉树后序遍历怎么看,希望您对编程的造诣更进一步.
这是我参与8月更文挑战的第20天，活动详情查看：8月更文挑战
说明:文章部分内容及图片出自网络，如有侵权请与我本人联系(主页有公众号:小攻城狮学前端)
作者：小只前端攻城狮、 主页：小只前端攻城狮的主页、 来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
【LeetCode 110.平衡二叉树】两种递归实现：自顶向下、自底向上
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
解法 1:自顶向下
根绝平衡二叉树的定义，可以递归比较每个节点的左右子树的高度差，是否超过 1。如果所有节点都满足条件，那么就是一棵平衡二叉树；否则，不是一棵平衡二叉树。
代码实现如下：
var isBalanced = function(root) {
if (!root) return true;
return (
isBalanced(root.left) &&
isBalanced(root.right) &&
Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
);
};
/** * 获取二叉树的高度 * @param {TreeNode} root * @return {number} */
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
解法 2: 自底向上（推荐）
你可能已经发现解法 1 的问题了：每个节点的高度值都会被重复计算。这带来了额外的时间消耗。那么如何避免这些重复计算呢？
解决思路是：先计算左右子树是否是平衡二叉树，并且计算、保存左右子树的高度，那么当前二叉树的高度可以通过左右子树的高度直接计算出来。
在 JavaScript 中，想要保存过程中的计算结果非常简单：可以通过传递一个对象作为参数，其上有属性 depth，表示以当前节点为根节点的二叉树的高度。
var isBalanced = function(root, obj = {}) {
if (!root) {
obj.depth = 0;
return true;
}
const left = {}; // 左子树信息
const right = {}; // 右子树信息
if (isBalanced(root.left, left) && isBalanced(root.right, right)) {
if (Math.abs(left.depth - right.depth) > 1) {
// 检查左右子树高度差
return false;
}
obj.depth = Math.max(left.depth, right.depth) + 1; // 当前二叉树的高度
return true;
} else {
return false;
}
};
感谢阅读，希望能对你有所帮助,文章若有错误或者侵权，可以在评论区留言或在我的主页添加公众号联系我。
写作不易，如果觉得不错，可以「点赞」+「评论」 谢谢支持❤
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/13730.html
