时间戳

首页 > 解决方案 > 判断二叉树是否平衡

python - 判断二叉树是否平衡

问题描述

基本上，此代码用于确定二叉树是否高度平衡。这是我的代码。

class Solution:
    """
    @param root: The root of binary tree.
    @return: True if this Binary tree is Balanced, or false.
    """
    def isBalanced(self, root):
        # write your code here
        if root is None:
            return

        left_height = self.findHeight(root.left)
        right_height = self.findHeight(root.right)
        print(root.val,left_height,right_height)
        self.isBalanced(root.left)
        self.isBalanced(root.right)
        if abs(left_height - right_height) > 1:
            return False
        return abs(left_height - right_height) <= 1

    def findHeight(self, root):
        if root is None:
            return 0
        left_height = self.findHeight(root.left)
        right_height = self.findHeight(root.right)
        height = max(left_height, right_height) + 1
        return height

对于下图中的二叉树二叉树打印的结果是

1 3 3
2 2 0
4 1 1
7 0 0
8 0 0
3 2 2
5 1 1
9 0 0
10 0 0
6 1 1
11 0 0
12 0 0

对于节点 2，left_height为 2 且right_height为 0，差值大于 1，应返回False。但是这段代码返回了True，我很困惑。

标签： pythonbinary-tree

解决方案

您的代码仅检查树顶部的高度是否正确。您需要考虑子树的结果。

这个

self.isBalanced(root.left)
self.isBalanced(root.right)
if abs(left_height - right_height) > 1:
    return False

应该是这个

return (
    self.isBalanced(root.left) and
    self.isBalanced(root.right) and
    abs(left_height - right_height) <= 1
)

推荐阅读