二分木の通りがけ順をMorris traversalで解く

二分木の値を通りがけ順に出力する問題。

再帰を使った深さ優先探索で解ける。

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

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return root
        
        self.ans=[]
        self.dfs(root)

        return self.ans
        
        
    def dfs(self, node):
        if node:
            self.dfs(node.left)
            self.ans.append(node.val)
            self.dfs(node.right)

モリスのアルゴリズム（ Morris Traversal ）を使うと、再帰を使わずに書くことが出来る。

仕組みとしては

１．左に子ノードがない場合、現在値を出力して右に進む。

２．左に子ノードがある場合、「左の子ノードの一番右のノード」の右側に、現在のノードの右側を移す。

３．１，２を繰り返す。

以下の例では現在地を分かりやすくするためにcurr=rootとしているが、rootのままでも解ける。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        curr = root
        ans = []
        while curr:
            if not curr.left:
                ans.append(curr.val)
                curr = curr.right
            else:
                leftchild = rightmost = curr.left
                while rightmost.right:
                    rightmost = rightmost.right
                
                rightmost.right = curr
                curr.left = None
                curr = leftchild
        
        return ans

参考

What is Morris traversal?

Contributor: Educative Answers Team

Inorder Tree Traversal without recursion and without stack! - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and prog...