いいものをつくろう

CTOの日記

アルゴリズム

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

投稿日:

こんにちは

今回の学びは

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

 

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

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

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

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

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

 

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

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

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

 

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

1つめの解法でいく。

 

 

4、実装しましょう。

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

 

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

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

エッジケースは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)

関連問題。

 

まとめ

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

 

以上です

-アルゴリズム
-, ,

Copyright© CTOの日記 , 2020 All Rights Reserved.