110. Balanced Binary Tree [easy] (Python)

タイトルリンク
https://leetcode.com/problems/balanced-binary-tree/
タイトル
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
タイトル翻訳
1本の二叉木を与えて、「高さバランス」の二叉木かどうかを判断します.
この問題について、「高さバランス」ツリーは、各ノードの2本のツリーの高さ差が1を超えないツリーとして定義されます.
考え方
考え方1
バランスツリーの定義に従って、2つの注意点があります:1、各ノードの2つのサブツリーもバランスツリーです.2,各ノードの2つのサブツリーの高さ差は1を超えない.直接的な考え方は、各ノードを遍歴し、各ノードの2つのサブツリーの高さ差が1(最初の再帰)以下であるかどうかを判断することである.一方,サブツリーの高さを求めるには再帰法(2番目の再帰)を用いることができる.
コード#コード#

# 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 root == None:
            return True

        left_depth = self.getDepth(root.left)
        right_depth = self.getDepth(root.right)
        if abs(left_depth - right_depth) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        else:
            return False

    def getDepth(self, root):
        if root == None:
            return 0
        return 1 + max(self.getDepth(root.left), self.getDepth(root.right))

このアルゴリズムの効率が低く,各ノードが高さを再計算し,大量の情報を浪費していることを示した.
考え方2
ノードの高さの繰返し計算を回避するために,TreeNodeノード構造におけるvalを用いて各ノードの高さを保存(または追加の辞書で保存)し,すべてのノードの高さを求めた後,DFSがバランスツリーであるか否かを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 root == None:
            return True

        self.getAllDepth(root)

        left_depth = root.left.val if root.left else 0
        right_depth = root.right.val if root.right else 0
        if abs(left_depth - right_depth) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        else:
            return False

    def getAllDepth(self, root):
        if root == None:
            return 0
        root.val = 1 + max(self.getAllDepth(root.left), self.getAllDepth(root.right))
        return root.val

思路三
構想1と構想2に基づいて,DFSを1回考慮し,各ノードの高さを求めるとともに,バランスツリーであるか否かを判断する.理論的には、各ノードへのアクセスは、バランスがとれているかどうか、ノードの高さが2つの値を返すべきであり、スペースを節約するために、-1でバランスがとれていない状態を表すと、変数を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 """
        return self.dfs(root) != -1

    def dfs(self, root):
        if root == None:
            return True

        left_depth = self.dfs(root.left)
        if left_depth == -1:
            return -1
        right_depth = self.dfs(root.right)
        if right_depth == -1:
            return -1

        return 1 + max(left_depth, right_depth) if abs(left_depth - right_depth) <= 1 else -1

PS:初心者はLeetCodeをブラシして、初心者はブログを書いて、書き間違えたり書いたりして、まだ指摘してください.ありがとうございます.転載は以下のことを明記してください.http://blog.csdn.net/coder_orz/article/details/51335758