剣指offerシリーズ-面接問題-面接問題55-II.バランスツリー(python)

文書ディレクトリ

1. タイトル

2. 解題構想

2.0再帰

3. コード実装

3.0再帰

4. まとめ

5. 参考文献

1.テーマ
ツリーのルートノードを入力し、ツリーがバランスツリーであるかどうかを判断します.あるツリーの任意のノードの左右のサブツリーの深さの差が1を超えない場合は、バランスのとれたツリーです.
2.問題の解き方
詳細は試験問題55-II.へいこうツリー
2.0再帰
木全体がバランスツリーであれば,各サブツリーがバランスツリーであり,再帰が利用できることは明らかである.
3.コード実装
3.0再帰

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        """
          ，                
        """
        def recur(root):
            if not root: return 0, True #         
            l, l_bal = recur(root.left) #       
            r, r_bal = recur(root.right) #       

            depth = l+1 if l > r else r+1 #     
            bal = l-r <= 1 if l > r else r-l <= 1
            return depth, bal and l_bal and r_bal #    ，   ，        

        _, flag = recur(root)
        return flag

4.まとめ
二叉木にとって、再帰のほうがいいです.難しいのは反復の書き方です.私はできません.
5.参考文献
[1]剣指offer叢書[2]剣指Offer-名企業面接官精講典型プログラミング問題[3]面接問題55-II.へいこうツリー