当前位置： 首页 > article >正文

码随想录算法训练营Day13 | 二叉树的各种遍历

article 2025/1/24 4:33:54

二叉树理论知识

文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

种类：

满二叉树
完全二叉树
二叉搜索树
平衡二叉搜索树

存储方式：

链式存储
线性存储

遍历方式

深度优先搜索（可用递归法、迭代法）：前序遍历、中序遍历、后序遍历
广度优先搜索（迭代法）：层序遍历

定义方式

class TreeNode:
	def __init__(self, val, left = None, right = None):
		self.val = val
		self.left = left
		self.right = right

递归遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html

前序

from typing import List, Optional

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


class Solution:
    def recursion(self, cur: Optional[TreeNode], l = List[int]) -> None:

        # 确定终止条件
        if cur == None:
            return None

        # 确定单层递归的逻辑
        # 前序遍历：中->左->右
        # 中
        l.append(cur.val)
        # 左
        self.recursion(cur.left, l)
        # 右
        self.recursion(cur.right, l)


    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        result = []

        self.recursion(root, result)

        return result

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

后序

class Solution:
    def recursion(self, cur : Optional[TreeNode], l : List[int]) -> None:
        
        # 确定终止条件
        if cur == None:
            return None

        # 确定单层递归逻辑
        # 左
        self.recursion(cur.left, l)
        # 右
        self.recursion(cur.right, l)
        # 中
        l.append(cur.val)


    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        result = []

        self.recursion(root, result)

        return result

中序

class Solution:
    def recursion(self, cur = Optional[TreeNode], l = List[int]) -> None:

        if cur == None:
            return None
        
        # 左
        self.recursion(cur.left, l)
        # 中
        l.append(cur.val)
        # 右
        self.recursion(cur.right, l)
        

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        result = []

        self.recursion(root, result)

        return result

迭代遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html

前序

class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''迭代法'''

        # 栈用来遍历节点元素
        stack = []
        # 列表用来存储结果
        result = []

        stack.append(root)

        while stack:
            node = stack[-1]
            stack.pop()

            # 若node不为空则加入到result中
            if node:
                result.append(node.val)
                # 先压入右子节点，出栈时右子节点后出，符合前序遍历的中左右中的右排最后
                stack.append(node.right)
                # 后压入左子节点，出栈时左子节点先出
                stack.append(node.left)
            else:
                continue

后序

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        '''
        整体思路为按照【中右左】的顺序用迭代法将树节点依次放入列表中，最后反转列表实现【左右中】
        '''

        stack = []
        result = []

        stack.append(root)

        while stack:
            node = stack[-1]       
            stack.pop()  # 记得要从栈中把元素弹出！

            if node:
                result.append(node.val)
                # 进栈时先进左子节点，则出栈时左子节点后出
                stack.append(node.left)
                # 进站时先进右子节点，则出栈时右子节点后出
                stack.append(node.right)
            else:
                continue
        
        # 记得还要反转列表
        # result = list(reversed(result))   #reversed() 函数用于反转一个可迭代对象（如列表、元组、字符串等）。它返回一个反转的迭代器，而不是直接返回一个列表，因此它的返回值是一个迭代器，你可以通过将其转换为列表、元组或其他数据结构来使用
        result = result[::-1]

        return result

中序 ！！！！

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''
        访问当前节点若不为空，则放入栈，指针再指向左孩子；若为空，则从栈中弹出元素，放入结果集，指针再指向右孩子
        '''

        # 用栈存放遍历过的元素
        stack = []
        # 用列表记录元素
        result = []

        cur = root

        while cur or stack:
            # 访问当前节点若不为空，则放入栈，代表已访问过当前节点，但还不用记录
            # 节点更新为左子节点
            if cur:
                stack.append(cur)
                cur = cur.left
            # 若为空，则从栈中弹出元素，记录该节点
            # 节点更新为右子节点
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right

        return result

统一迭代

题目链接/文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html

空指针法

以后序为例

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        '''
        统一迭代法中，访问的节点和要处理的节点不一致，
        所以当访问过的节点入栈时，在该类节点后再放入空指针Null，表示已访问但未处理
        '''

        stack = []
        result = []

        # 加上if root防止碰到空输入
        if root:
            stack.append(root)

        while stack:
            node = stack.pop()

            # 若该node不为空，则说明该node未被访问过，按照中右左的顺序依次将节点放入站，并在该node后放入null
            if node:
                # 中
                stack.append(node)
                stack.append(None)

                # 右：注意注意！！！一定要判断是否确定有左右孩子，有才放进栈中，否则若直接不加判断就放入（空）孩子，会和用来标记的空指针混淆
                if node.right:   
                    stack.append(node.right)
                # 左
                if node.left:
                    stack.append(node.left)

            # 若node为空，表示该节点之前已被访问过，此时可以处理该节点了
            else:
                node = stack.pop()
                result.append(node.val)

        return result

boolean值法

以后序为例

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        '''
        boolean统一迭代法中，访问的节点和要处理的节点不一致，
        所以给每个节点进栈时加一个Boolean值标记。
        boolean为True代表之前已经访问过该节点，可以进行收割；False表示首次访问，此次访问目的为将该节点及其左右孩子放入栈中
        '''

        stack = [(root, False)] if root else []
        result = []

        while stack:

            node, boolean = stack.pop()

            # boolean为true表示已访问该节点，可以进行收割
            if boolean:
                result.append(node.val)
            
            # boolean为false表示首次访问。此次访问的目的是“把自己和两个儿子在栈中安排好位次”
            # 但一定要判断左右孩子是否存在，存在才有必要放入栈中
            # 因为是后序遍历，则进栈顺序为中右左
            else:
                # 中
                stack.append((node, True))

                # 右
                if node.right:
                    stack.append((node.right, False))

                # 左
                if node.left:
                    stack.append((node.left, False))


        return result

层序遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        '''
        将每层的节点依次放入队列中，并记录每层结点的个数
        '''

        result = []

        # 队列用来按层依次放入节点
        # 注意这里要用deque[root]而不是deque(root)
        que = deque([root]) if root else deque()

        # 只要que有元素，就代表这一层有节点
        while que:
            # 先确定该层有多少个节点
            size = len(que)
            LevelResult = []

            # 每一次循环中将出队元素的左右孩子节点（若有）依次放入队列中
            # 出队元素记录在每一层的临时结果中
            for _ in range(size):
                node = que.popleft()
                LevelResult.append(node.val)
                # 一定要判断孩子是否存在啊！！！！！
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)

            result.append(LevelResult)

        return result

时间复杂度：O(n)，因为每个节点只遍历了一次


http://www.kler.cn/a/515823.html

相关文章：

  • .NET 9 微软官方推荐使用 Scalar 替代传统的 Swagger
  • 探索WPF中的RelativeSource：灵活的资源绑定利器
  • 基于微信小程序的童装商城的设计与实现（LW+源码+讲解）
  • Flutter 改完安卓 applicationId 后App 闪退问题。
  • Redis vs. 其他数据库：深度解析，如何选择最适合的数据库？
  • 解锁C# EF/EF Core：从入门到进阶的技术飞跃
  • Android设备：Linux远程lldb调试
  • Avalonia：C# 跨平台桌面应用的优秀选择
  • Android Audio音频系统
  • solidity基础 -- 存储类型
  • 快速入门Flink
  • 电子电气架构 --- 智能电动汽车电子与其软件架构
  • 隐藏php版本信息x-powered-by
  • 【Uniapp-Vue3】setTabBar设置TabBar和下拉刷新API
  • 如何提升flink的处理速度？
  • 解决 VMware Workstation Pro 中 Linux 虚拟机无法拖放文件及共享文件夹挂载问题
  • 基于 WPF 平台实现成语游戏
  • 深入理解 Spring 的 Lazy Loading：原理、实现与应用场景
  • 【HeadFirst系列之HeadFirst设计模式】第3天之观察者模式
  • 激光雷达和相机早期融合
  • 利用现有模型处理面部视频获取特征向量(1)
  • # [Unity基础] 游戏物体与组件的关系
  • 【IEEE Fellow 主讲报告| EI检索稳定】第五届机器学习与智能系统工程国际学术会议（MLISE 2025）
  • Nginx 与后端服务的集成配置
  • 文本文件打印类库(C#)
  • The Surprising Effectiveness of Test-Time Training for Abstract Reasoning