首页 > 编程语言 >代码随想录算法训练营第十八天 | 513.找树左下角的值,112. 路径总和,113.路径总和ii,106.从中序与后序遍历序列构造二叉树,105.从前序与中序遍历序列构造二叉树

代码随想录算法训练营第十八天 | 513.找树左下角的值,112. 路径总和,113.路径总和ii,106.从中序与后序遍历序列构造二叉树,105.从前序与中序遍历序列构造二叉树

时间:2023-12-31 22:33:54浏览次数:50  
标签:结点 遍历 递归 int 中序 二叉树 序列

一、513.找树左下角的值

题目链接:

LeetCode 513.找树左下角的值

学习前:

思路:

层序遍历。采用递归和迭代两种方式

  • 递归:定义最大深度和目标值两个成员变量,方法参数是结点和当前结点的深度;返回类型为void;终止条件为结点为空;单次循环内容为判断该节点是否符合目标要求,且分别传入左子树和右子树,且深度分别加一,进行递归调用
  • 迭代:new一个队列,存层次遍历的结点,取每一层的第一个结点值进行赋值,遍历结束后即为所求

学习后:

进行代码优化。对于递归,判断该节点是否符合目标要求作为终止条件,且在递归调用左子树和右子树时进行判空

二、112. 路径总和

题目链接:

LeetCode 112. 路径总和

学习前:

思路:

前序遍历。采用递归方式

  • 递归:定义sum累加从根结点到叶子结点的和
    • 方法参数:(TreeNode root, int targetSum, int sum)
    • 返回类型:boolean
    • 终止条件:结点为空返回false;碰到叶子结点,满足目标返回true,反之返回false
    • 单次循环内容:首先在终止条件之间加入sum累加当前结点值,接着此时的结点一定非空且非叶子结点,故若左子树存在,则递归调用左孩子,若结果返回true,则返回true;右子树同理;本次循环若在这些地方都没返回,则返回false

学习后:

  • 不用额外定义sum,直接用targetSum做减法,判断是否为0即可

三、113.路径总和ii

题目链接:

LeetCode 113.路径总和ii

学习前:

思路:

前序遍历。采用递归方式

  • 递归:定义sum累加从根结点到叶子结点的和

    • 方法参数:(TreeNode root, int targetSum),其中成员变量List res是结果集合,成员变量List per是单条路径值集合
    • 返回类型:void
    • 终止条件:结点为空;碰到叶子结点,其中若符合题意则res.add
    • 单次循环内容:若左右孩子存在,则分别进行递归调用,且回溯per,删除最后一个元素

学习后:

将成员变量List res和List per降为方法参数,减小内存开销

四、106.从中序与后序遍历序列构造二叉树

题目链接:

LeetCode 106.从中序与后序遍历序列构造二叉树

学习前:

思路:

递归

  • 方法参数:(int[] inorder, int[] postorder)
  • 返回类型:TreeNode
  • 终止条件:if(inorder.length0) return null;if(inorder.length1) return root;
  • 单次循环内容:
    1. 确定根结点即后序遍历最后一个值
    2. 找到中序遍历的根结点下标index
    3. 根据index将中序遍历切割成左中序和右中序两个数组
    4. 根据第3步切割的数组的长度将后序遍历切割成左后序和右后序两个数组
    5. 递归调用

学习后:

  • 在对中序数组和后续数组进行切割时,不用再额外开辟新数组,通过下标进行访问,即方法参数变为(int[] inorder, int inorder_start, int inorder_end, int[] postorder, int postorder_start, int postorder_end)
  • 注意对终止条件和单次循环内容的改写

五、105.从前序与中序遍历序列构造二叉树

题目链接:

LeetCode 105.从前序与中序遍历序列构造二叉树

学习后:

思路:

递归

  • 方法参数:(int[] preorder, int[] inorder)
  • 返回类型:TreeNode
  • 终止条件:if(inorder.length0) return null;if(inorder.length1) return root;
  • 单次循环内容:
    1. 确定根结点即前序遍历第一个值
    2. 找到中序遍历的根结点下标index
    3. 根据index将中序遍历切割成左中序和右中序两个数组
    4. 根据第3步切割的数组的长度将前序遍历切割成左前序和右前序两个数组
    5. 递归调用

六、学习总结

  1. 时间:5.5h
  2. 通过遍历顺序构建唯一二叉树
  3. 递归需要返回值和无需返回值的情况

标签:结点,遍历,递归,int,中序,二叉树,序列
From: https://www.cnblogs.com/amulet/p/17938162

相关文章

  • 二叉树的四种遍历-前序、中序、后序、层序
    目录一、易懂的形象理解1、先序遍历2、中序遍历3、后序遍历4、层序遍历二、真正理解三种遍历一、易懂的形象理解其实从名字就可以很好的理解这三种遍历,我在第二点时候说,但是估计能翻到我的文的同学们之前肯定看过好多类似的了,那咱们换个思路~先用我想的一种简单易懂的形象思维......
  • 二叉树遍历(C语言版)
    二叉树遍历先序递归int*res;voidpreorder(structTreeNode*root,int*returnSize){if(root==NULL)return;//根左右res[(*returnSize)++]=root->val;preorder(root->left,returnSize);preorder(root->right,returnSize);}int*pre......
  • 力扣543-二叉树的直径
    难度:【简单】定义:在一个二叉树中,任意两个节点之间的路径中最长的路径的长度称为其直径。路径长度由两个节点之间经过的“边”表示,而不是节点数。且二叉树的直径不一定经过根节点。先大致看了官方解法,不理解,心情暴躁没看懂,就自己瞎写。起初不理解直径不一定经过根节点。根据示......
  • 代码随想录算法训练营第12天 | 树的遍历
    (本合集全部为Go语言实现)相关文章链接:递归遍历迭代遍历统一迭代法相关视频链接:Leetcode94状态:实现过程中的难点:迭代法的模拟过程比较难想个人写法递归方式funcinorderTraversal(root*TreeNode)[]int{varres[]intinorderTraversal0(root,&res)return......
  • 二叉树面试题解析
    二叉树面试题解析判断相同的树/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNode......
  • 算法学习Day18左下角的值,路径总和,构建二叉树
    #Day18左下角的值,路径总和,构建二叉树`ByHQWQF2023/12/30`##笔记***##513.找树左下角的值给定一个二叉树的**根节点**`root`,请找出该二叉树的 **最底层 最左边**节点的值。假设二叉树中至少有一个节点。**示例2:****输入:**\[1,2,3,4,null,5,6,null,null,7]**......
  • JAVA 实现 - 二叉树(二)
    二叉搜索树二叉搜索树/二叉查找树/二叉排序树特点:树节点增加key属性,用来比较谁大谁小,key不可以重复对于任意一个树节点,它的key比左子树的key都大,同时也比右子树的key都大/***二叉搜索树*/publicclassBSTree1{publicTreeNoderoot;publicstaticcla......
  • 算法学习Day17二叉树迭迭迭迭代
    Day17迭迭迭迭代ByHQWQF2023/12/28笔记110.平衡二叉树给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树_每个节点_的左右两个子树的高度差的绝对值不超过1。示例1:输入:root=[3,9,20,null,null,15,7]输出:true递归法......
  • 代码随想录算法训练营第十七天 | 110.平衡二叉树,257. 二叉树的所有路径,404.左叶子之和
    一、110.平衡二叉树题目链接:LeetCode110.平衡二叉树学习:思路:后序遍历。实际上是由叶结点到根结点,若有一颗子树不是平衡二叉树,则直接返回给根结点二、257.二叉树的所有路径题目链接:LeetCode257.二叉树的所有路径学习:思路:递归+回溯。因为是线=先遍历根结点,然后遍历左孩......
  • [BIG2015] 2. 基于操作码序列和TextCNN分类
    目录构建词表构建整数索引语料构建dataset和dataloader构建训练函数和推理函数训练、推理和结果分析导入包:importpandasaspdimportosimportnumpyasnpimportmatplotlib.pyplotaspltfromsklearn.feature_extraction.textimportCountVectorizer#For......