- Notifications
You must be signed in to change notification settings - Fork45
Open
Description
仰望星空的人，不应该被嘲笑
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树[3,9,20,null,null,15,7]3/ \920/ \157返回true。
示例 2:
给定二叉树[1,2,2,3,3,null,null,4,4]1/ \22/ \33/ \44返回false。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
dfs，平衡二叉树就是每个节点 的左右两个子树的高度差的绝对值不超过1。那么，我们可以自底向上，即采用后序遍历的方式，只要左右高度超过1了，直接设置flase即可。
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } *//** *@param {TreeNode} root *@return {boolean} */varisBalanced=function(root){if(!root)returntrue;letres=true;letdfs=(root)=>{// 先遍历左子树，在遍历右子树letleft=root.left&&dfs(root.left)+1;letright=root.right&&dfs(root.right)+1;// 判断是否是平衡二叉树，就看高度差是否大于1if(Math.abs(left-right)>1)res=false;// 返回左右子树深度的最大值returnMath.max(left,right);}dfs(root);returnres;};
最后
文章产出不易，还望各位小伙伴们支持一波！
往期精选：
leetcode-javascript：LeetCode 力扣的 JavaScript 解题仓库，前端刷题路线（思维导图）
小伙伴们可以在Issues中提交自己的解题代码，🤝 欢迎Contributing，可打卡刷题，Give a ⭐️ if this project helped you!
访问超逸の博客，方便小伙伴阅读玩耍~
学如逆水行舟，不进则退