【LeetCode】二叉树各种遍历大汇总（秒杀前序、中序、后序、层序）递归 & 迭代

相似题目：

1. 【LeetCode】572. 另一个树的子树
2. 【LeetCode】104. 二叉树的最大深度【简单】
3. 【LeetCode】110. 平衡二叉树
4. 【LeetCode】297. 二叉树的序列化与反序列化【困难】
5. 【LeetCode】226.翻转二叉树
6. 【LeetCode】235. 二叉搜索树的最近公共祖先

LeetCode 原题地址
7. 144. 二叉树的前序遍历
8. 94. 二叉树的中序遍历
9. 145. 二叉树的后序遍历
10. 102. 二叉树的层序遍历

1. 递归（前、中、后序）

# 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]:
    """ 前序遍历 递归"""
        ans = []
        def helper(root):
            if not root:
                return
            ans.append(root.val)  # 前序遍历，root -> left -> right
            helper(root.left)
            helper(root.right)
        helper(root)
        return ans

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        """ 中序遍历 递归"""
        ans = []
        def helper(root):
            if not root:
                return
            helper(root.left)
            ans.append(root.val)    # 中序遍历，left -> root -> right
            helper(root.right)
        helper(root)
        return ans
        
    def postorderTraversal(self, root: TreeNode) -> List[int]:
       """ 后序遍历 递归"""
        ans = []
        def helper(root):
            if not root:
                return 
            helper(root.left)
            helper(root.right)
            ans.append(root.val)   # 后序遍历，left -> right -> root
        helper(root)
        return ans

2. 迭代（前、中、后、层序）

# 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]:
"""前序遍历 迭代"""
# T = root # 可以用临时变量，以防修改原始数据
stack = []        
preData = []
while (root or stack):           # 树不空，或者堆栈不空
while root:                  # 只要节点不是 None，即树不空，就一直把节点压入堆栈，并且一直往左走到死胡同里，结束循环
stack.append(root)       # 入栈（第一次碰到）
preData.append(root.val) # 前序遍历是第一次碰到就输出
root = root.left         # 一直往左走，并一直压入堆栈
# 上述压栈循环结束，跳出
if stack:                         
root = stack.pop()       # 出栈（第二次碰到，中序遍历就是放在这里之后），开始往回走，pop出 root
root = root.right        # 继续往右走
return preData
def inorderTraversal(self, root: TreeNode) -> List[int]:
""" 中序遍历 迭代 """
T = root
stack = []
inData = []
while (T or stack):
while T:
stack.append(T)       # 第一次碰到
T = T.left
if stack:
T = stack.pop()      # pop 出 root，即第二次碰到
inData.append(T.val) # 第二次碰到之后输出
T = T.right
return inData
def postorderTraversal(self, root: TreeNode) -> List[int]:
""" 后序遍历 迭代 和前序遍历的区别是把 left/right 互换，最后再把获得的数据逆序输出"""
T = root
stack = []
postData = []
while (T or stack):
while T:
stack.append(T)
postData.append(T.val)
T = T.right               # 先 right，再 left
if stack:
T = stack.pop()
T = T.left
return postData[::-1]             # 最后逆序输出
def levelOrder_1D(self, root: TreeNode) -> List[List[int]]:
""" 层序遍历 迭代 BFS 输出一维列表 [3,9,20,null,null,15,7] => [3,9,20,15,7]"""
T = root
if not T:
return
queue = []
levelData = []
queue.append(T)
while queue:
T = queue.pop(0)         # 取出队首元素
levelData.append(T.val)  # 并且输出
if T.left:
queue.append(T.left)
if T.right:
queue.append(T.right)
return levelData
def levelOrder_2D(self, root: TreeNode) -> List[List[int]]:
""" 层序遍历 迭代 BFS 输出二维列表 [3,9,20,null,null,15,7] => [[3],[9,20],[15,7]]"""
T = root
if not T:
return[]
queue = []
ans = []                     # 最终二维列表答案
level = []                   # 每一层
queue.append(T)              # 入队
curCount, nextCount = 1, 0   # 当前层节点数、下一层节点数
while queue:
T = queue.pop(0)         # 出队
level.append(T.val)       
curCount = curCount - 1  # 每输出一个当前层的节点，把当前层节点数减去 1
if T.left:                      # 左子树
queue.append(T.left)
nextCount = nextCount + 1   # 每添加一个下一层节点，则把下一层节点数加 1
if T.right:                     # 右子树
queue.append(T.right)
nextCount = nextCount + 1
if curCount == 0:               # 当前层节点数量为 0，表示当前层已经输出完毕，需要访问下一层
ans.append(level)           # 一层一层添加
curCount = nextCount   
nextCount = 0               # 置零，等待重新计数
level = []
return ans

参考：

1.LeetCode题解 & 评论

本文地址：https://blog.csdn.net/weixin_41888257/article/details/107142724