平衡二叉树平衡因子怎么计算_LeetCode 题解 | 110.平衡二叉树

本期精选题解由我们的用户“Krahets”倾情撰写，一起来看看吧！110.平衡二叉树平衡二叉树 - 力扣（LeetCode）leetcode-cn.com题目描述给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例 1:给定二叉树 [3,9,20,null,null,15,7]3/9...

weixin_39533174

973人浏览 · 2020-11-21 13:03:40

weixin_39533174 · 2020-11-21 13:03:40 发布

本期精选题解由我们的用户“Krahets”倾情撰写，一起来看看吧！

110.平衡二叉树

平衡二叉树 - 力扣（LeetCode）leetcode-cn.com

题目描述

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

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

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

解决方案

从底至顶（提前阻断法）

对二叉树做深度优先遍历DFS，递归过程中：
终止条件：当DFS越过叶子节点时，返回高度0；
返回值：
从底至顶，返回以每个节点root为根节点的子树最大高度(左右子树中最大的高度值加1max(left,right) + 1)；
当我们发现有一例 左/右子树高度差＞ 1 的情况时，代表此树不是平衡树，返回-1；
当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回-1，避免后续多余计算。
最差情况是对树做一遍完整 DFS，时间复杂度为 O(N)。

Python

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.depth(root) != -1

    def depth(self, root):
        if not root: return 0
        left = self.depth(root.left)
        if left == -1: return -1
        right = self.depth(root.right)
        if right == -1: return -1
        return max(left, right) + 1 if abs(left - right) < 2 else -1J

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        return depth(root) != -1;
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;
        int right = depth(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

从顶至底（暴力法）

构造一个获取当前节点最大深度的方法 depth() ，通过比较左右子树最大高度差abs(self.depth(root.left) - self.depth(root.right))，来判断以此节点为根节点下是否是二叉平衡树；
从顶至底 DFS，以每个节点为根节点，递归判断是否是平衡二叉树：
若所有根节点都满足平衡二叉树性质，则返回 True ；
若其中任何一个节点作为根节点时，不满足平衡二叉树性质，则返回False。
本方法产生大量重复的节点访问和计算，最差情况下时间复杂度 O(N^2)。

Python

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root: return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and 
            self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root):
        if not root: return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

本文作者：Krahets

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐