平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例:
输入:root = [3,9,20,null,null,15,7]
输出:true
1
2
2
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
if(root===null) return true
let res =true
function traverse(root){
let l=helper(root.left)
let r=helper(root.right)
console.log(l,r,"-")
if(Math.abs(l-r)>1) {
res=false
return
}
if(root.left) traverse(root.left)
if(root.right) traverse(root.right)
}
traverse(root)
return res
};
function helper(root){
let max =0
let ans =0
function dfs(root){
if(root===null) return
ans++
max=Math.max(ans,max)
dfs(root.left)
dfs(root.right)
ans--
}
dfs(root)
return max
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/balanced-binary-tree/