当前位置: 首页 > news >正文

力扣刷题-二叉树-二叉树的递归遍历

本文讲解二叉树的前序遍历、后序遍历、中序遍历。

思路

每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!
确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
参考:https://www.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#%E6%80%9D%E8%B7%AF(以c++为例更容易理解)

前序遍历(144)

# Definition for a binary tree node.
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root: # 确定终止条件return []# 单层递归逻辑left = self.preorderTraversal(root.left)right = self.preorderTraversal(root.right)return [root.val] + left + right # 用[]存储结果

后序遍历(145)

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []left = self.postorderTraversal(root.left)right = self.postorderTraversal(root.right)return left + right + [root.val]

中序遍历(94)

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []left = self.inorderTraversal(root.left)right = self.inorderTraversal(root.right)return left + [root.val] + right
http://www.lryc.cn/news/218148.html

相关文章:

  • VX-3R APRS发射试验
  • JAVA毕业设计109—基于Java+Springboot+Vue的宿舍管理系统(源码+数据库)
  • CMU/MIT/清华/Umass提出生成式机器人智能体RoboGen
  • STM32:AHT20温湿度传感器驱动程序开发
  • 【Linux】第七站:vim的使用以及配置
  • 汇编-算术运算符
  • 线性代数 第六章 二次型
  • leetCode 213. 打家劫舍 II + 动态规划 + 从记忆化搜索到递推 + 空间优化
  • 网络编程套接字(二)
  • [极客大挑战 2019]Knife 1(两种解法)
  • 国家统计局教育部各级各类学历教育学生情况数据爬取
  • mysql、clickhouse时间日期加法
  • 21.合并两个有序链表
  • thinkphp漏洞复现
  • 暴力递归转动态规划(十三)
  • java EE 进阶
  • 记录paddlepaddle-gpu安装
  • django如何连接sqlite数据库?
  • 面试算法47:二叉树剪枝
  • 云安全-云原生k8s攻击点(8080,6443,10250未授权攻击点)
  • 性能压力测试主要目标及步骤
  • VLAN与配置
  • API接口安全设计
  • 服务器的管理口和业务口
  • 【gpt redis】原理篇
  • python二次开发Solidworks:排雷以及如何排雷?
  • 广告引擎检索技术快速学习
  • Scala的类和对象
  • SQL中 <>(不等于)运算符只会匹配那些具有非空值的记录
  • 冒泡排序(Java)