二叉树 | 迭代遍历 | leecode刷题笔记

跟随carl代码随想录刷题
语言：python

---

二叉树的迭代遍历——深度优先

统一迭代法推荐

将要访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记（要处理的节点放入栈之后，紧接着放入一个空指针做标记）。

前序遍历、中序遍历、后序遍历迭代法代码的唯一区别就是下面三个子句的顺序：

• if node.right: st.append(node.right) # 右节点进栈
• if node.left: st.append(node.left) # 左节点进栈
• st.append(node)st.append(None) # 中节点进栈
  • 把握一个原则：进栈顺序与出栈顺序相反
  • 前序遍历期望的出栈顺序是中 左 右，所以进栈顺序是右 左 中
  • 中序遍历期望的出栈顺序是左 中 右，所以进栈顺序是右 中 左
  • 后序遍历期望的出栈顺序是左 右 中，所以进栈顺序是中 右 左

---

思路分析——以中序遍历为例

思路分析——以中序遍历为例（中序遍历的顺序是：左中右）

• 首先将根节点压入栈中，作为开始遍历的起点
• 遍历开始
  • 只要当前节点不为空，就弹出当前节点，对当前节点进行下一步检查（压栈顺序右中左与出栈顺序相反）：
    • 如果当前节点的右节点存在，就压入栈中
    • 把当前节点压入栈中，再压入一个空节点️这一步是一定会执行的
    • 如果根节点的左节点存在，就压入栈中

经过一次遍历操作之后，我们会得到以下两种情况的栈内容：

• 当前节点的左节点存在：st = [……, 中, None, 左]
  • 此时需要进一步遍历左节点的右左子树，再次进行上述迭代
• 当前节点的左节点不存在：st = [……, 中， None]
  • 说明当前节点已到达最底部，不用再遍历，可以直接存入结果集。
  • 而None就是作为是否可以存入结果集的标记：如果弹出为None，就继续再弹出一个，并将其存入结果集。

举个例子吧：

94. 二叉树的中序遍历——迭代法

# 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]:
        result = []
        st = []

        if root:
            st.append(root)  # 根节点压入栈
        while st:
            node = st.pop()  # node等于根节点
            if node != None:
                if node.right:  # 如果右节点存在，就压入栈
                    st.append(node.right)
                
                """ 1. 中节点压入栈 2. 再压入一个空节点 因为中节点访问过，但是还没有处理，加入空节点作为标记 """
                st.append(node)  
                st.append(None)  
                
                if node.left:  # 如果左节点存在，则压入栈
                    st.append(node.left)
            else:  # 只有遇到空节点的时候，才将下一个节点放入结果集
                node = st.pop()  # 重新取出栈中元素
                result.append(node.val)  # 存入结果集
        return result

144. 二叉树的前序遍历——迭代法

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        st = []

        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right:
                    st.append(node.right)
                if node.left:
                    st.append(node.left)
                st.append(node)
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

145. 二叉树的后序遍历——迭代法

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        st = []

        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                st.append(node)
                st.append(None)

                if node.right:
                    st.append(node.right)
                if node.left:
                    st.append(node.left)

            else:
                node = st.pop()
                result.append(node.val)

        return result

---

附：另一种写法emm……看一下就行

前序遍历（迭代法）

• 先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子，这样，出栈的时候就是中左右的顺序。注意：根节点最开始就出栈
  

• 定义共分两部分：

  • 处理：将元素放进result数组中
  • 访问：遍历节点

因为前序遍历要访问和处理的元素都是中间节点，所以代码写起来简单。

完整代码如下（不推荐）

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 根节点为空则返回空列表
        if not root:
            return []

        stack = [root]  # 否则，先将根节点压入栈中
        result = []  # 初始化一个空列表用于存放结果集

        while stack:
            node = stack.pop()  # 
            # 中节点先处理
            result.append(node.val)  # 结果集中存入中节点的值
            # 右孩子先入栈
            if node.right:  # 如果当前节点的右孩子存在，就入栈
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:  # 如果当前节点的左孩子存在，就入栈
                stack.append(node.left)
        return result 

BUT!!! 中序遍历和后序遍历没有办法在前序遍历的基础上进行调整，而是需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。。好麻烦