Leetcode094. Middle order traversal of binary trees

094. Middle order traversal of binary trees

Given a binary tree, return its middle-order traversal. Non-recursively, use iteration.

# 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
""" """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ """ The core idea is as follows: use color to mark the status of nodes. New nodes are white, and visited nodes are gray. If the encountered node is white, it is marked gray, and its right child, itself, and left child are pushed in order. If a grey node is encountered, the value of the node is printed. If you want to realize the sequential traversal before and after, you only need to adjust the pushing order of the left and right child nodes. "" "
Copy the code