preorder, postorder, levelorderをiterativeに実装する

木の巡回操作はrecursiveだと直感的だし

実装も簡単ですが、iterativeで解かない解けない場面のために

解けるようにしたいが、これは練習が必要である。

この問題や【アルゴリズム脳トレ】leetcode easy 589 N-ary tree preorder traversal

この問題を通して　【アルゴリズム脳トレ】leetcode easy 589 N-ary tree preorder traversal

実践したのだが、どうも難しい。多少慣れた気はしている。二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明

でまとめてみたりもしている。

ここでは、

一つにシンプルな実装方法をマスターとしてここに記す。

忘れたときにここに戻ってきて思い出すのに役立ててほしい。

百聞は一見にしかず

注目したいのは、これらはN-aryということで2分木ではなく、子供が複数もてるという点だ。

ということで実装はこちら

# https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/460888/Simple-Iterative-Python-Solutiono
# こいつをpostorderに改造する
class Solution:
    def __preorder(self, root):
        stack = [root]; res = []
        while len(stack) > 0:
            current = stack.pop()
            res.append(current.val)
            if current.children:
                for node in current.children[::-1]:
                    stack.append(node)
        return res

    def __levelorder(self, root):
        stack = [root]; res = []
        while len(stack) > 0:
            current = stack.pop(0)
            res.append(current.val)
            if current.children:
                for node in current.children:
                    stack.append(node)
        return res

    """
    thanks I finally understand it by looking this solution.
    https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/432121/Python-Intuitive-Iterative-Solution-One-Stack
    """
    def __postorder(self, root):
        stack = [root]; res = []
        while len(stack) > 0:
            current = stack.pop()
            res.insert(0, current.val)
            if current.children:
                for node in current.children:
                    stack.append(node)
        return res

    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        print("preorder: %s" % self.__preorder(root))
        print("levelorder: %s" % self.__levelorder(root))
        print("postorder: %s" % self.__postorder(root))

# n1 = Node(1)
# n2 = Node(2)
# n3 = Node(3)
# n4 = Node(4)
# n5 = Node(5)
# n6 = Node(6)
#
# n1.children = [n3, n2, n4]
# n3.children = [n5, n6]

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)
n8 = Node(8)
n9 = Node(9)
n10 = Node(10)
n11 = Node(11)
n12 = Node(12)
n13 = Node(13)
n14 = Node(14)

n1.children = [n2, n3, n4, n5]
n3.children = [n6, n7]
n7.children = [n11]
n11.children = [n14]
n4.children = [n8]
n5.children = [n9, n10]
n8.children = [n12]
n9.children = [n13]

ans = Solution().postorder(n1)
print(ans)

コードは

https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/432121/Python-Intuitive-Iterative-Solution-One-Stack

と

https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/460888/Simple-Iterative-Python-Solutiono

を引用させて頂いている。

2分木のinorderも例もついでに乗せておく

こちらです。https://leetcode.com/problems/binary-tree-inorder-traversal/

class Solution_rec:
    def __init__(self):
        self.ans = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.dfs(root)
        return self.ans
    def dfs(self, root: TreeNode) -> List[int]:
        if root is None: return
        self.dfs(root.left)
        self.ans.append(root.val)
        self.dfs(root.right)
        return

class Solution_iterative:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack, order = [], []
        curr = root
        while curr or len(stack) > 0:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                order.append(curr.val) # inorder
                curr = curr.right
        return order

以上です