二叉树遍历的循环解

94 Binary Tree Inorder Traversal

二叉树中序遍历的循环解

常规思路：

向左找到尽头，弹出一个节点，指针指向弹出节点的右孩子 继续循环

def inorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    # if not root:
    #     return []
    res, stack = [], []
    p = root
    while stack or p: # 中序遍历处理完左侧分支和根节点之后 栈空 所以只用stack做条件不合理
        while p:
            stack.append(p)
            p = p.left
        cur = stack.pop() # 左边走到尽头 弹出最左节点
        res.append(cur.val)
        # while stack and not cur.right: # 希望弹出的节点的右孩子存在  这样就找到一个接盘侠 类似于递归的感觉
        #     cur = stack.pop() # 但是你怎么能保证就存在呢? p 还是有可能是空的 所以不用折腾
        #     res.append(cur.val)
        p = cur.right # 很像递归
    return res

将两层while循环简化成一层 仔细分析和上面的代码思路一抹一样

def inorderTraversal(self, root):
    res, stack = [], []
    p = root # 定义一个指针
    while stack or p:
        if p: # 进栈 往左
            stack.append(p)
            p = p.left
        else: # 出栈 往右 (左边走到尽头)
            node = stack.pop()
            res.append(node.val)
            p = node.right # 尝试向右边跑 如果这个节点存在 就是递归 不存在 就继续弹出栈内节点
    return res

节点状态标记法

中序遍历顺序：左根右
难点在于访问到根节点的时候并不是现在就要处理该节点（打印该节点）
而是要去该节点的左孩子继续向下访问，
只有当左孩子部分全部处理完毕，再次访问到根节点的时候才是处理根节点的时候
所以给每一个节点设置一个状态，用于标记该节点之前是否见过，当某个节点第二次访问的时候就是该处理的时候

def inOrder(root):
    res, stack = [], [(root, False)]
    while stack:
        node, vis = stack.pop()
        if node:
            if vis:
                res.append(node.val)
            else: # 注意堆栈元素顺序和根左右恰好相反
                stack.append((node.right, False))
                stack.append((node, True))
                stack.append((node.left, False))
    return res

二叉树前序遍历、后序遍历循环解 leetcode 144 145

对于前序遍历，因为根节点一开始就被用掉，所以很方便

def preorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        if node:
            # pre-order, right first 这样left位于栈顶 所以是根左右
            res.append(node.val)
            stack.append(node.right)
            stack.append(node.left) 
    return res

对于后序遍历 根节点最后处理 所以需要一直在栈底

节点状态标记法

对于每一个节点给一个状态，用于标记这个节点是第一次访问还是第二次访问，第二次访问才是真正处理该节点的时候（打印该节点）

def postorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    res, stack = [],  [(root, False)]
    while stack:
        node, vis = stack.pop()
        if node:
            if vis: # 左右孩子处理完毕
                res.append(node.val)
            else:
                stack.append((node, True)) # 成功地将根节点放在了栈底
                stack.append((node.left, False))
                stack.append((node.right, False))
    return res

二叉树的层序遍历