[leetcode] 110。バランス二分木@python



110 Balanced Binary Tree Python



元の質問

二分木が与えられた場合、それが高さのバランスが取れているかどうかを判断します。

この問題では、高さのバランスが取れた二分木は次のように定義されます。



すべてのノードの2つのサブツリーの深さが1を超えて異ならないバイナリツリー。

例1:



次のツリー[3,9,20、null、null、15,7]があるとします。

3

/
920
/
15 7
trueを返します。

例2:



次のツリーが与えられた場合[1,2,2,3,3、null、null、4,4]:

1 / 2 2 /

3 3
/
4 4
falseを返します。

解決策1

再帰的に、高さ関数を定義してノードの高さを計算し、各サブツリーの高さの差が1より大きいかどうかを比較し、大きい場合はFalseを返します。
最悪の場合:O(n)+ 1/2 * O(n / 2)+ 1/4 * O(n / 4)+…

時間:O(n * log(n))
スペース:O(1)

コード

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isBalanced(self, root): ''' :type root: TreeNode :rtype: bool ''' if not root: return True left_depth = self.depth(root.left) right_depth = self.depth(root.right) if abs(left_depth - right_depth) <= 1: return self.isBalanced(root.left) and self.isBalanced(root.right) else: return False def depth(self, node): if not node: return 0 return max(self.depth(node.left), self.depth(node.right)) + 1

解決策2

1つのトラバーサルでは、深さ関数を定義します。左側のサブツリーまたは右側のサブツリーが不均衡である場合、またはそれらの高さの差が1より大きい場合は、不均衡を表す-1を返します。それ以外の場合は、検索を続行します。最後に、深度関数が-1であるかどうかを確認します
時間:O(n)
スペース:O(1)

コード

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isBalanced(self, root): ''' :type root: TreeNode :rtype: bool ''' def depth(root): # base case if not root: return 0 left_depth = depth(root.left) right_depth = depth(root.right) if left_depth == -1 or right_depth == -1 or abs(left_depth- right_depth) > 1: return -1 return max(left_depth, right_depth) + 1 return depth(root) != -1