python二叉树中序遍历迭代法

迭代法遍历二叉树：左根右

# 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: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root] #存放具有左子树的根节点
        numArrray = []
        while( stack != [] ):
            root = stack.pop()
            while(root.left or root.right): #当前结点有子节点
                while(root.left) : #存在左节点则一直往左遍历并保存
                    p = root.left
                    root.left = None  #遍历过的根节点左节点置零
                    stack.append(root)#避免重复遍历
                    root = p
                if root.right: #当前节点不存在左节点但存在右节点
                    numArrray.append(root.val)#输出当前节点
                    root = root.right #往右走一步
            numArrray.append(root.val)#当前节点是子节点，直接输出           
        
        return numArrray