【アルゴリズム脳トレ】leetcode easy 101 symmetric tree

投稿日：2019年12月27日

こんにちは

今回の学びは

・木は締めトリック右と左が同じか？左の右と右の左が同じか？の分割統治法で(再起でも)倒せる

問題はhttps://leetcode.com/problems/symmetric-tree/

（時間配分は5分問題理解　10分検討 10分実装 20分振り返り　の一文45分構成)

終始、わからないことは声にだして、明確にしていきましょう。

１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると）

nullがあたえられたらどうする？=> trueでいいか。

２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析を付け加えて）

１つは、levelorderを配列に格納して、それをvalidateする。O(N)解法。

２つは、dfs（）でもハッシュマップで自分のlayer層と何番目の子供か？という情報があればなんとかトラックできるとおもうが、worstケースの計算が悪いので、

３，どれでいくか、一緒に決定しましょう。

１つめの解法でいく。

４、実装しましょう。

class Solution:
    def validate(self, layer: List[int]):
        #print("layer:%s" % layer)
        if layer is None or len(layer) == 0: True
        l = 0
        r = len(layer) - 1
        while l <= r:
            #print("layer[l]:%s != layer[r]:%s" % (layer[l], layer[r]))
            if layer[l] != layer[r]: return False
            l += 1
            r -= 1
        return True

    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None: return True

        stack = [root]
        while len(stack) > 0:
            layer_stack = []
            layer = [n.val if n else 'null' for n in stack]
            # validate layer
            if not self.validate(layer): return False
            for n in stack:
                if n:
                    layer_stack += [n.left, n.right]
            stack = layer_stack
        return True

５、エッジケースとサンプルテストを忘れずに！

サンプルケースで声にだして、しゃべってみた。

エッジケースはnullくらい。

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは？」

level-orderでのtraverseが基本。

（これで詰まるならここで復習せよ。【アルゴリズム脳トレ】leetcode medium 429 N-ary tree inorder traversal)

他の人の解法紹介。

再起の解法はhttps://leetcode.com/problems/symmetric-tree/discuss/460626/Python-Code%3A-Faster-than-99

考え方は、木は締めトリック右と左が同じか？左の右と右の左が同じか？の分割統治法で倒せる

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:

        def rec(node1, node2):
            if node1 is None and node2 is None: return True
            if node1 is None and node2: return False
            if node1 and node2 is None: return False
            # どっちもノード有り
            if node1.val != node2.val: return False
            # ここは味噌。n1の左と右を比較している訳ではないことに注意!
            return rec(node1.left, node2.right) and rec(node1.right, node2.left)

        if root is None: return True
        return rec(root.left, root.right)

(explained https://leetcode.com/problems/symmetric-tree/discuss/461798/Python-Iterative-and-Recursive-solution)