首页 > 其他分享 >代码随想录 day17 平衡二叉树 二叉树的所有路径 左叶子之和

代码随想录 day17 平衡二叉树 二叉树的所有路径 左叶子之和

时间:2024-01-12 23:22:36浏览次数:19  
标签:递归 代码 随想录 叶子 这题 day17 二叉树 回溯

平衡二叉树

之前一直写迭代代码 没有怎么写递归
正好这题不是很好写迭代 练习一下递归

这题递归逻辑相对简单
左右子树高度差判断是不是大于一 可以直接返回结果
不大于一就高度max(l,r)+1

二叉树的所有路径

关键要点 这题适合先序遍历
回溯过程和递归过程是一起写的
进来几次就回溯几次
这样才能回归到合适位置

精简版本的代码为什么可以不用回溯
由于精简版本的使用的是值拷贝而不是引用
那么回退到上一层节点时 其实path值未发生改变 相当于每一层有一个临时变量
只有到叶子才会被收集 收集完了就回退到根(或者满足左右子树的其他节点)接着收集

左叶子之和

这题比较适合用后序遍历进行递归
因为左叶子需要父节点判断 实际上就是先走到下面再回来

标签:递归,代码,随想录,叶子,这题,day17,二叉树,回溯
From: https://www.cnblogs.com/mingtiao/p/17961782

相关文章

  • [代码随想录] 第一天
    704.二分查找[https://leetcode.cn/problems/binary-search/description/]思路:二分查找适用于在有序数组中查找目标值,左边边界为left,右边边界为right,每次使用middle=(right+left)/2,将原数组划分为[left,middle]和[middle,right]两个数组,若middle<target,则目标值落在右边数组,否......
  • day13 代码随想录算法训练营 递归遍历
    题目:144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历我的感悟:用helper内部函数写更好理解难点: 代码难点:代码示例:前序#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#......
  • 代码随想录算法训练营第二十四天 | 回溯算法理论基础,77. 组合
    一、回溯算法理论基础学习:1.基本概念回溯法是一种搜索方式回溯的本质是穷举,是递归的副产品,即回溯算法就是递归算法回溯解决的问题都能理解成树形结构,一般是在集合中递归查找子集。集合的大小构成树的宽度(n叉树),递归的深度构成了树的深度2.回溯解决的问题(1)组合问题:N个......
  • 代码随想录 day10 栈模拟队列 队列模拟栈
    栈模拟队列大概了解一下思路自己就可以很快写出来了我们需要第二个辅助栈帮助我们把stackIn的顺序颠倒,这样FILO的栈颠倒后pop的顺序就和FIFO的队列顺序一致了大概就是这张图队列模拟栈题目要求使用两个队列模拟栈其实可以只需要一个队列就可以模拟栈的出栈顺序是最后......
  • 二叉树解题思路小记
    二叉树前中后序位置代码框架voidtraverse(TreeNoderoot){if(root==null){return;}//前序位置traverse(root.left);//中序位置traverse(root.right);//后序位置}代码写在不同的位置,只是执行的时间不同。前序位置刚刚进入二......
  • 代码随想录算法训练营第二十天|654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,9
    一、654.最大二叉树题目链接:LeetCode654.最大二叉树学习:思路:前序遍历方法参数:(int[]nums,intstart,intend)返回类型:TreeNode终止条件:if(end-start==0)returnnull;if(end-start==1)returnnewTreeNode(nums[start]);单层递归逻辑:寻找数组中的最大......
  • 代码随想录 小结02 链表
    第一题移除链表元素这题比较简单使用dummyHead的方式会比较简单不需要对头指针进行单独处理但是空间开销会大一些第二题设计链表类这个没什么好说的感觉有可能一些细节会忘记需要经常复习的一块第三题反转链表这题难度不大用一个tmp指针存储一下当前指针的next......
  • 代码随想录算法训练营第十八天 | 513.找树左下角的值,112. 路径总和,113.路径总和ii,106.
    一、513.找树左下角的值题目链接:LeetCode513.找树左下角的值学习前:思路:层序遍历。采用递归和迭代两种方式递归:定义最大深度和目标值两个成员变量,方法参数是结点和当前结点的深度;返回类型为void;终止条件为结点为空;单次循环内容为判断该节点是否符合目标要求,且分别传入左子......
  • 代码随想录 小结01 数组
    数组篇一共有五个题目第一题二分查找值得注意的是,要自己想好区间的边界到底是写左闭右开还是左闭右闭根据边界不同while的条件和左右指针的移动会有差别目前我的习惯是写左闭右开还是固定一下习惯比较好第二题是实现数组类的erase()使用快慢指针可以做到在数组原地进......
  • 二叉树的四种遍历-前序、中序、后序、层序
    目录一、易懂的形象理解1、先序遍历2、中序遍历3、后序遍历4、层序遍历二、真正理解三种遍历一、易懂的形象理解其实从名字就可以很好的理解这三种遍历,我在第二点时候说,但是估计能翻到我的文的同学们之前肯定看过好多类似的了,那咱们换个思路~先用我想的一种简单易懂的形象思维......