迭代法遍历二叉树:左根右
# 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