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

Binary Tree Inorder Traversal - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

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

# 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 )を使うと、再帰を使わずに書くことが出来る。

仕組みとしては

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

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

3.1,2を繰り返す。

以下の例では現在地を分かりやすくするために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?
Creator: Edpresso 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 programming articles, quizzes and practice/c...




 

コメント

タイトルとURLをコピーしました