一.题目

leetcode:110

二.题目与解析

扫盲

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


这里可以看一个大佬的视频:
https://leetcode-cn.com/problems/balanced-binary-tree/solution/shu-ju-jie-gou-he-suan-fa-ping-heng-er-c-ckkm/
视频很生动。
这道题也是用递归
而且:深度可以从上到下去查 所以需要前序遍历(中左右),而高度只能从下到上去查,所以只能后序遍历(左右中)
先确认一下各个环节:

  • 参数与返回值
    参数是每一次的当前节点,返回值为以当前节点为根节点的树的高度
    其中,-1表示已经不是平衡二叉树了,否则返回的是以该节点为根节点的二叉树的高度。
    如果当前传入节点为根节点的二叉树已经不是二叉平衡树了,还返回高度的话就没有意义了。
    所以如果已经不是二叉平衡树了,可以返回-1 来标记已经不符合平衡树的规则了。

  • 终止条件
    当前节点为nil

  • 单层递归逻辑
    左右子树高度差值的绝对值小于等于1则返回高度,否则返回-1
    注意result要加上当前层。

func isBalanced(root *TreeNode) bool {
    if getHeight(root)==-1{
        return false
    }
    return true
}

func getHeight(root *TreeNode)int{
    if root==nil{
        return 0
    }
    // 左
    leftHeight := getHeight(root.Left)
    if leftHeight==-1{
        return -1
    }
    // 右
    rightHeight := getHeight(root.Right)
    if rightHeight == -1{
        return -1
    }
    result := 0
    // 中
    if math.Abs(float64(leftHeight)-float64(rightHeight))>1{
        result = -1
    }else{
        result = max(leftHeight, rightHeight) + 1
    }
    return result
}
func max(left, right int)int{
    if left>right{
        return left
    }
    return right
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:191 个
  • 运行天数:1006 天
  • 访问总数:124261 人次

浙公网安备33011302000604

辽ICP备20003309号