LeetCode.94ツリーの中順遍歴(python解法)

目次

題

solution_1

参考資料

タイトル
二叉木を指定し、その中序遍歴を返します.
例:

  : [1,null,2,3]
   1
    \
     2
    /
   3

  : [1,3,2]

solution_1
構想:「色マーク法」は、スタック反復法の効率を兼ね備え、再帰法のように簡潔で分かりやすく、さらに重要なのは、この方法は前序、中序、後序に遍歴し、完全に一致したコードを書くことができることである.
その核心思想は以下の通りである.

は、ノードの状態を色でマークし、新しいノードは白で、アクセスしたノードはグレーです.

遭遇したノードが白色である場合、それを灰色としてマークし、右サブノード、自身、左サブノードを順次スタックに入れる.

遭遇したノードがグレーの場合、ノードの値が出力されます.

結果:実行時間:44 msランキング:77.00%勝利
コードは次のとおりです.

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

参考資料
ツリーの中順ループカラーマーキング法