leetcode [94] 二叉树的中序遍历

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个二叉树，返回它的中序 遍历。

示例:

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

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路来自题解:着色标记

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack = [(0, root)]
        result = []
        while stack:
            color, node = stack.pop()
            if color == 0:
                if node.right:
                    stack.append((0, node.right))
                stack.append((1, node))
                if node.left:
                    stack.append((0, node.left))
            else:
                result.append(node.val)

        return result