平衡二叉树
平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true。给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false。题解
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
var target = true;
var dfs = function(root){
if(!root) return 0;
if(!target) return 0;
var l = dfs(root.left);
var r = dfs(root.right);
if(Math.abs(l-r)>1) target = false;
return l > r ? l+1 : r+1;
}
dfs(root);
return target;
};思路
定义一个深度递归遍历的函数，在一个节点中获取树的左右子树的高度，也就是定义获取树的高度的函数，在获取左右子树的高度时比较左右子树是否平衡即可，首先定义目标变量target，之后定义深度递归遍历dfs函数，在函数中判断节点不存在则返回0，接下来是一部分剪枝，如果已经找到了不平衡的位置那么就没有必要继续向下遍历，之后定义l为左子树的高度，r为右子树的高度，之后进行比较如果做右子树的高度差大于1则认为其不是平衡二叉树，赋值target为false，之后返回做右子树中高的子树的高度+1，执行dfs深度递归遍历，完成后返回target即可。
每日一题
https://github.com/WindrunnerMax/EveryDay参考
https://leetcode-cn.com/problems/balanced-binary-tree/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
