LeetCode 0110.平衡二叉树

平衡二叉树

LeetCode110. 平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

题外话

这里强调一波概念：

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：

求深度可以从上到下去查所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

本题思路

既然要求比较高度，必然是要后序遍历。

递归三步曲分析：

明确递归函数的参数和返回值
- 参数：当前传入节点。
- 返回值：以当前传入节点为根节点的树的高度。
明确终止条件
- 递归的过程中遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
明确单层递归的逻辑
- 分别求出传入节点的左右子树的高度，若差值≤1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了

代码

Go

 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
48
49
50
51
52
53


type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

//传入一个结点,判断以该节点为根的树是否为平衡二叉树,若是返回true,否则返回false
func isBalanced(root *TreeNode) bool {
    //若传入结点为空,则直接返回true
    if root == nil {
        return true
    }
    //若传入结点的左右子树只要有一个不是平衡二叉树,则直接返回false
    if !isBalanced(root.Left) || !isBalanced(root.Right) { //递归
        return false
    }
    //求出以传入节点为根的左右子树的最大深度
    LeftH := maxDepth(root.Left)
    RightH := maxDepth(root.Right)
    //若以传入节点为根的左右子树的最大深度差的绝对值超过1,则返回false,否则返回true
    if abs(LeftH-RightH) > 1 {
        return false
    }
    return true
}

//传入一个结点,返回以该节点为根的树的最大深度
func maxDepth(root *TreeNode) int {
    //若传入结点为空,则直接返回0
    if root == nil {
        return 0
    }
    //得到传入结点的左右子树的最大深度
    maxLR := max(maxDepth(root.Left), maxDepth(root.Right)) //递归
    //上面求出的是以传入节点为根的左右子树的最大深度,返回值要+1表示以传入节点为根的树的最大深度
    return maxLR + 1
}

//比较传入两个的数字,返回大的数字
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

//返回传入数字的绝对值
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Link

GitHub