T94 二叉树的中序遍历

题目描述如下：

直接用迭代的方法：

可以将中序遍历看作是两种操作，一个是经过，一个是输出，输出了的部分就不能再次输出了，要防止重复输出，但是经过并不影响输出，经过只是判断还有左子树，暂时不能输出。

整个过程如下：判断当前是否为空，如果不是，则判断有无左子树，如果有左子树，则经过此结点到达左子树；如果为空，说明上一个结点没有右子树，取出栈中栈顶元素输出，经过该节点到右子树。反复进行。

# 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]:
       res = []
       mystack = []
       while stack or root:
           if root:
               mystack.append(root)
               root = root.left
           else:
               tmp = mystack.pop()
               rest.append(tmp.val)
               root = tmp.right
       return rest

结果如下：