代码随想录算法训练营第十四天|二叉树基础-二叉树迭代-二叉树

2024-01-25 04:52
文章标签 算法 基础 随想录 代码 二叉树 训练营 迭代 第十四天

本文主要是介绍代码随想录算法训练营第十四天|二叉树基础-二叉树迭代-二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 二叉树基础
    • 二叉树种类
      • 满二叉树
      • 完全二叉树
      • 二叉搜索树
      • 平衡二叉搜索树
    • 二叉树的存储方式
      • 链式存储
      • 顺序存储
    • 二叉树的遍历方式
    • 二叉树的定义
  • 二叉树的递归遍历
    • 144.二叉树的前序遍历
      • 代码：
    • 145.二叉树的后序遍历
      • 代码：
    • 94. 二叉树的中序遍历
      • 代码
  • 二叉树的迭代遍历
    • 前序遍历（迭代法）-中左右->中右左（模拟出入栈）
      • 代码
    • 后序遍历（迭代法）
      • 思路：
      • 代码：
    • 中序遍历（迭代法）
      • 代码：
  • 二叉树的统一迭代法-画图理解增加熟练
      • 前序遍历写法-右左中（反过来）
      • 中序遍历写法-右中左
    • 后序遍历-中右左

二叉树基础

二叉树种类

满二叉树

在这里插入图片描述

完全二叉树

在这里插入图片描述

二叉搜索树

在这里插入图片描述

平衡二叉搜索树

在这里插入图片描述

二叉树的存储方式

链式存储

在这里插入图片描述

顺序存储

在这里插入图片描述

二叉树的遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  1. 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  2. 广度优先遍历
    • 层次遍历（迭代法）
      在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中
    在这里插入图片描述

二叉树的定义

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

二叉树的递归遍历

在这里插入图片描述

144.二叉树的前序遍历

前序遍历，中左右

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();//结果数组preorder(root,result);//开始从根节点遍历return result;}public void preorder(TreeNode root,List<Integer> res){if(root==null){return; //直接返回}res.add(root.val);//添加根节点preorder(root.left,res);preorder(root.right,res);}
}

145.二叉树的后序遍历

左右中

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postOrder(root,res);return res;}public void postOrder(TreeNode root,List<Integer> res){if(root==null){return;}postOrder(root.left,res);postOrder(root.right,res);res.add(root.val);}
}

94. 二叉树的中序遍历

左中右

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inOrder(root,res);return res;}public void inOrder(TreeNode root,List<Integer> res){if(root==null){return;}inOrder(root.left,res);res.add(root.val);inOrder(root.right,res);}
}

二叉树的迭代遍历

前序遍历（迭代法）-中左右->中右左（模拟出入栈）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，
那么先将根节点放入栈中，
然后先将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

动画如下：
在这里插入图片描述

代码

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();if(root==null){return res;}Stack<TreeNode> stack=new Stack<>();stack.push(root);//加入根节点while(!stack.isEmpty()){//中TreeNode node=stack.pop();//弹出根节点res.add(node.val);//储存根节点的数值//右if(node.right!=null){stack.push(node.right);}//左if(node.left!=null){stack.push(node.left);}}return res;}
}

后序遍历（迭代法）

思路：

前序遍历的数组储存是中左右，那么把函数翻转，则变成数组储存是中右左，再将数组进行翻转，则变成左右中。
在这里插入图片描述

代码：

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack=new Stack<>();if(root==null){return res;}stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();res.add(node.val);if(node.left!=null){stack.push(node.left);}if(node.right!=null){stack.push(node.right);}}Collections.reverse(res);//反转数组return res;}
}

中序遍历（迭代法）

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点
    分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

动画如下：
在这里插入图片描述

代码：

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}

二叉树的统一迭代法-画图理解增加熟练

在这里插入图片描述

前序遍历写法-右左中（反过来）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();if(root!=null){stack.push(root);}while(!stack.isEmpty()){TreeNode node=stack.peek();//栈中的第一个节点if(node!=null){stack.pop();//弹出避免重复，下面再将右左中节点添加到栈中if(node.right!=null){//添加右节点，空节点不入栈stack.push(node.right); }if(node.left!=null){//添加左节点，空节点不入栈stack.push(node.left);}stack.push(node);//添加中节点stack.push(null);//中节点还没有处理，添加空节点null做标记}else{stack.pop();//弹出nullnode=stack.peek();//重新取出栈中元素stack.pop();//取出后再弹出res.add(node.val);}}return res;}
}

中序遍历写法-右中左

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root!=null){//先放入根节点stack.push(root);}while(!stack.isEmpty()){TreeNode node = stack.peek();//查找第一个结点if(node!=null){stack.pop();//弹出重复节点，按顺序放入右中左if(node.right!=null){stack.push(node.right);}stack.push(node);stack.push(null);if(node.left!=null){stack.push(node.left);}}else{stack.pop();node = stack.peek();stack.pop();res.add(node.val);}}return res;}
}

后序遍历-中右左

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root!=null){//先放入根节点stack.push(root);}while(!stack.isEmpty()){TreeNode node = stack.peek();//查找第一个结点if(node!=null){stack.pop();//弹出重复节点，按顺序放入中右左stack.push(node);stack.push(null);if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}}else{stack.pop();node = stack.peek();stack.pop();res.add(node.val);}}return res;}
}

这篇关于代码随想录算法训练营第十四天|二叉树基础-二叉树迭代-二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/642140。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2