LeetCode 第 110 题: 平衡二叉树 Balanced Binary Tree
文章目录
这颗平衡二叉树的要求是,
每一个结点的左子树和右子树的高度差,不超过 1
错误理解:
1, 这颗二叉树的深度 - 其最浅的结点深度 <= 12, 不能存在只有左边叶子的结点、只有右边叶子的结点
解决:
遍历每一个结点,拿到其左叶子的深度和其右叶子的深度,比较下 OK
求取深度与比较叶子结点的深度,可以同时处理掉
求取深度,用递归,就是自底而上,拿到结点的左叶子结点深度和右叶子结点深度,
这时候,顺便来一个比较,就好了
class Solution {
func depth(node root:TreeNode?) -> Int?{
guard let n = root else {
return 0
}
guard let lhs = depth(node: n.left), let rhs = depth(node: n.right), abs(rhs - lhs) <= 1 else{
return nil
}
return max(lhs, rhs) + 1
}
func isBalanced(_ root: TreeNode?) -> Bool {
guard let n = root else {
return true
}
return depth(node: n) != nil
}
}
其中有一句
guard let lhs = depth(node: n.left) else{
return nil
}这个是,左子树的结果不满足,则最终的结果(我们寻求的)也不满足
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论