关于算法:LeetCode-第-110-题-平衡二叉树-Balanced-Binary-Tree

这颗均衡二叉树的要求是,

每一个结点的左子树和右子树的高度差,不超过 1

谬误了解:

1, 这颗二叉树的深度 – 其最浅的结点深度 <= 1

2, 不能存在只有右边叶子的结点、只有左边叶子的结点


解决:

遍历每一个结点,拿到其左叶子的深度和其右叶子的深度,比拟下 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
        }

这个是,左子树的后果不满足,则最终的后果(咱们寻求的)也不满足

github 链接

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理