一套模板应对二叉树的前序中序后序遍历(迭代实现)

前言

今天在leetcode刷关于二叉树的题目,然后就是涉及了这个二叉树的遍历。

使用递归,可以很快的解决这个遍历问题,但是,好像在实际应用过程中,是不建议使用递归来使用的。

并且,很多题目,都要求最好是用迭代法来解决,提升下能力。

先贴上leetcode的相关题目链接

  • 前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal

  • 中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal

  • 后序遍历

https://leetcode-cn.com/problems/binary-tree-postorder-traversal

练习算法,整理笔记,巩固知识

现在有这么一个二叉树,先了解下前序,中序,后序遍历的基本规则

2020/03/31/77ae80331054551.png

前序:先
1432

中序:先
3412

后序:先
3421

下面这一篇是一个中序遍历的题解,这个方法,可以轻松应对,前序中序后序的迭代法遍历。

我下面的代码,均是按照这个方法来做的。

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/

模板

# 新建两个列表,res用于输出,stack当做一个栈
# 入栈操作(节点,状态),False表示,还未被遍历,True则表示已遍历过
res, stack = [], [(root, False)]
    # 循环遍历这个栈    
    while stack: 
        # 出栈,node表示当前节点,vis表示当前节点的状态
        node, vis = stack.pop() 
        # 判断当前节点是否有效
        if node:
            # 判断当前节点的状态,True代表已经遍历过,遍历过就加入到列表中
               if vis:
                   res.append(node.val)
            # 否则,就是暂未被遍历
               else:
                   stack.append((node.right, False))
                   stack.append((node.left, False))
                   stack.append((node, True))
            # 还未被遍历,这里就需要考虑遍历的顺序了。
            # 这里拿前序遍历举例,我们知道其遍历顺序为:根节点->左孩子节点->右孩子节点
            # 然后,栈的特点是啥? '后进先出,先进后出'
            # 所以按照前序的遍历顺序,我们这里的入栈操作,顺序为右节点,左节点,根节点
            # 根据遍历的要求,更改这里的遍历顺序,即可以不变应万变,解决前序中序后序

前序遍历

算法

从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        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.left, False))
                    stack.append((node, True))
        return res

中序遍历

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        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

后序遍历

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> 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.right, False))
                    stack.append((node.left, False))
        return res
添加新评论