文化礼堂建设情况网站,江西宜春市建设局网站,有哪些企业公司,石景山老山网站建设废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【二叉树的遍历】#xff0c;使用【二叉树】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【二叉树的遍历】使用【二叉树】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。 就着这两个高频题目把二叉树的遍历类型题目刷一遍
名曲目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
二叉树的前序遍历【EASY】
前序、中序、后序都有迭代和递归的实现方式
题干 解题思路
前序遍历简单来说就是“根左右”展开来说就是对于一颗二叉树优先访问其根节点然后访问它的左子树等左子树全部访问完了再访问其右子树而对于子树也按照之前的访问方式直到到达叶子节点每次访问一个节点之后它的左子树是一个要前序遍历的子问题它的右子树同样是一个要前序遍历的子问题。那我们可以用递归处理
终止条件 当子问题到达叶子节点后后一个不管左右都是空因此遇到空节点就返回。返回值 每次处理完子问题后就是将子问题访问过的元素返回依次存入了数组中。本级任务 每个子问题优先访问这棵子树的根节点然后递归进入左子树和右子树。
具体做法 step 1准备数组用来记录遍历到的节点值Java可以用List step 2从根节点开始进入递归遇到空节点就返回否则将该节点值加入数组。 step 3依次进入左右子树进行递归。
代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构无 算法递归、DFS 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param root TreeNode类* return int整型一维数组*/public int[] preorderTraversal (TreeNode root) {// 1 定义用来返回的数据ListInteger list new ArrayList();// 2 递归填充list的值preorder(list, root);// 3 返回结果处理int[] result new int[list.size()];for (int i 0; i list.size(); i) {result[i] list.get(i);}return result;}private void preorder(ListInteger list, TreeNode root) {// 1 递归终止条件if (root null) {return;}// 2 按顺序递归填充左右子树list.add(root.val);preorder(list, root.left);preorder(list, root.right);}
}复杂度分析
时间复杂度遍历了N个节点所以时间复杂度为ON 空间复杂度最坏情况下树退化为链表递归栈深度为N所以空间复杂度为ON
二叉树的中序遍历【EASY】
换位中序遍历
题干 解题思路
如果一棵二叉树对于每个根节点都优先访问左子树那结果是什么从根节点开始不断往左第一个被访问的肯定是最左边的节点。然后访问该节点的右子树最后向上回到父问题。因为每次访问最左的元素不止对一整棵二叉树成立而是对所有子问题都成立因此循环的时候自然最开始都是遍历到最左然后访问然后再进入右子树我们可以用栈来实现回归父问题
寻找最左子树此过程逐层将树及左子树的根节点压入栈中把要后处理的上层子树根节点先压入操作栈栈顶即当前最左子树根节点也是上层子树的左子节点将值放入到list节点指针移动到当前指针右节点如果右节点为空则本层处理完成栈再弹出上层节点接着循环处理
其实思路与递归就相似了只不过将递归栈具象化了
代码实现
递归的思路和代码不再赘述直接给出
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param root TreeNode类* return int整型一维数组*/public int[] inorderTraversal (TreeNode root) {// 1 定义入参和返回值ListInteger list new ArrayList();// 2 中序递归获取listinorder(list, root);// 3 list结果转换int[] result new int[list.size()];for (int i 0; i list.size(); i) {result[i] list.get(i);}return result;}private void inorder(ListInteger list, TreeNode root) {// 1 终止条件if (root null) {return;}inorder(list, root.left);list.add(root.val);inorder(list, root.right);}
}给出代码实现基本档案 基本数据结构二叉树 辅助数据结构栈、DFS 算法迭代 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param root TreeNode类* return int整型一维数组*/public int[] inorderTraversal (TreeNode root) {// 1 定义入参和辅助栈ListInteger list new ArrayList();StackTreeNode stack new StackTreeNode();if (root null) {return new int[0];}// 2 寻找最左子树TreeNode tempRoot root;while (tempRoot ! null || !stack.isEmpty()) {// 2-1 寻找最左子树此过程逐层将树及左子树的根节点压入栈中while (tempRoot ! null) {// 把要后处理的上层子树根节点先压入操作栈stack.push(tempRoot);tempRoot tempRoot.left;}// 2-2 栈顶即当前最左子树根节点也是上层子树的左子节点TreeNode node stack.pop();list.add(node.val);// 2-3 节点指针移动到当前指针右节点如果右节点为空则本层处理完成栈再弹出上层节点tempRoot node.right;}// 3 list结果转换int[] result new int[list.size()];for (int i 0; i list.size(); i) {result[i] list.get(i);}return result;}
}复杂度分析
时间复杂度遍历了N个节点所以时间复杂度为ON 空间复杂度最坏情况下树退化为链表辅助递归栈深度为N所以空间复杂度为ON
二叉树的后序遍历【EASY】
ok再来看二叉树的后序遍历
题干 解题思路
左右根同前序遍历及中序遍历的递归解法不再赘述
代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构无 算法递归、DFS 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param root TreeNode类* return int整型一维数组*/public int[] postorderTraversal (TreeNode root) {// 1 定义用来返回的数据ListInteger list new ArrayList();// 2 递归填充list的值postorder(list, root);// 3 返回结果处理int[] result new int[list.size()];for (int i 0; i list.size(); i) {result[i] list.get(i);}return result;}private void postorder(ListInteger list, TreeNode root) {if (root null) {return;}postorder(list, root.left);postorder(list, root.right);list.add(root.val);}
}复杂度分析
时间复杂度遍历了N个节点所以时间复杂度为ON 空间复杂度最坏情况下树退化为链表递归栈深度为N所以空间复杂度为ON
二叉树的层序遍历【MID】
二叉树的层序遍历
题干 解题思路
二叉树的层次遍历就是按照从上到下每行然后每行中从左到右依次遍历得到的二叉树的元素值。对于层次遍历我们通常会使用队列来辅助
因为队列是一种先进先出的数据结构我们依照它的性质如果从左到右访问完一行节点并在访问的时候依次把它们的子节点加入队列那么它们的子节点也是从左到右的次序且排在本行节点的后面因此队列中出现的顺序正好也是从左到右正好符合层次遍历的特点
step 1首先判断二叉树是否为空空树没有遍历结果。step 2建立辅助队列根节点首先进入队列。不管层次怎么访问根节点一定是第一个那它肯定排在队伍的最前面。step 3每次进入一层统计队列中元素的个数。因为每当访问完一层下一层作为这一层的子节点一定都加入队列而再下一层还没有加入因此此时队列中的元素个数就是这一层的元素个数。step 4每次遍历一层的节点数将其依次从队列中弹出然后加入这一行的一维数组中如果它们有子节点依次加入队列排队等待访问。step 5访问完这一层的元素后将这个一维数组加入二维数组中再访问下一层。 代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构队列 算法迭代、BFS 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param root TreeNode类* return int整型ArrayListArrayList*/public ArrayListArrayListInteger levelOrder (TreeNode root) {// 1 定义要返回的数据结构ArrayListArrayListInteger result new ArrayList();// 2 定义辅助队列结构每次队列都只存一层QueueTreeNode queue new LinkedListTreeNode();// 3 首先将第一层也就是根节点放入队列if (root null) {return new ArrayList();}queue.add(root);// 4 核心处理逻辑分层获取元素并加入列表while (!queue.isEmpty()) {ArrayListInteger levelList new ArrayListInteger();// 需要用一个临时变量承接队列大小否则每次新加一层永远无法遍历完本层int queueSize queue.size();for (int i 0; i queueSize; i) {// 4-1 获取队首元素当前层元素并添加到层列表中TreeNode node queue.poll();levelList.add(node.val);// 4-2 分别将节点左右元素添加到队列尾部if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}// 4-3 将本层元素集合添加到结果集中result.add(levelList);}return result;}
}复杂度分析
时间复杂度遍历了一遍树时间复杂度为ON 空间复杂度使用了辅助队列空间复杂度为ON
二叉树的锯齿形层序遍历【MID】
难度升级每层要反过来
题干 解题思路
解题思路与层次遍历相同只不过需要隔行反转。只需增加标志位即可。
代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构队列 算法迭代、BFS 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param pRoot TreeNode类* return int整型ArrayListArrayList*/public ArrayListArrayListInteger Print (TreeNode pRoot) {// 1 定义返回结果ArrayListArrayListInteger result new ArrayList();if (pRoot null) {return new ArrayList();}// 2 定义队列并将根节点放入QueueTreeNode queue new LinkedList();queue.add(pRoot);// 3 设置反转标志位隔行反转boolean isReverse false;// 4 核心逻辑将数据放入结果集while (!queue.isEmpty()) {int queueSize queue.size();ArrayListInteger levelList new ArrayListInteger();for (int i 0; i queueSize; i ) {TreeNode node queue.poll();levelList.add(node.val);if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}// 依据标志位结果进行层级数据反转if (isReverse) {Collections.reverse(levelList);}// 重置标志位以便下一层反转isReverse !isReverse;result.add(levelList);}return result;}
}复杂度分析
时间复杂度遍历了一遍树时间复杂度为ON 空间复杂度使用了辅助队列空间复杂度为ON
二叉树的右视图【MID】
使用深度优先搜素方法
题干 解题思路
我们可以对二叉树进行层次遍历那么对于每层来说最右边的结点一定是最后被遍历到的。二叉树的层次遍历可以用广度优先搜索实现。
执行广度优先搜索左结点排在右结点之前这样我们对每一层都从左到右访问。因此只保留每个深度最后访问的结点我们就可以在遍历完整棵树后得到每个深度最右的结点 所以只要按照层序遍历的思路把每一层的最后一个节点放到结果集就行了。
代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构队列 算法迭代、BFS 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 求二叉树的右视图* param root 树的根节点* param inOrder int整型一维数组 中序遍历* return int整型一维数组*/public ListInteger rightSideView(TreeNode root) {// 1 定义返回的结果集ListInteger result new ArrayListInteger();if (root null) {return new ArrayListInteger();}// 2 定义队列用来容纳每一层节点QueueTreeNode queue new LinkedListTreeNode();queue.add(root);// 3 遍历每一层并获取最右边的节点while (!queue.isEmpty()) {int queueSize queue.size();for (int i 0; i queueSize; i) {TreeNode node queue.poll();if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}// 如果节点是本层最后一个节点则添加到结果集中if (i queueSize - 1) {result.add(node.val);}}}return result;}}复杂度分析
时间复杂度 O(N)每个节点都入队出队了 1 次。 空间复杂度 O(N)使用了额外的队列空间。
拓展知识深度优先遍历和广度优先遍历
广度优先搜索BFS和深度优先搜索DFS是两种经典的图遍历算法它们也可以用于二叉树的遍历和搜索。以下是它们的定义以及在二叉树中的应用场景
广度优先搜索BFS
BFS是一种图遍历算法它从一个起始节点开始逐层地遍历与该节点相邻的节点然后再遍历与这些相邻节点相邻的节点以此类推。BFS通常使用队列数据结构来实现。
在二叉树中的应用场景
层级遍历BFS可以用于按层级遍历二叉树从根节点开始逐层遍历可以方便地实现层级顺序的操作。查找最小深度BFS可以用于查找二叉树的最小深度即从根节点到最近叶子节点的最短路径。查找特定元素如果您需要在二叉树中查找特定元素BFS可以用于在树中搜索一旦找到目标元素就可以停止搜索。判断是否为完全二叉树BFS可以用于判断二叉树是否是完全二叉树通过观察层级遍历的结果可以检查每一层是否都填满节点。
深度优先搜索DFS
DFS是一种图遍历算法它从一个起始节点开始沿着一条路径一直深入到无法继续前进的节点然后返回上一层继续探索其他路径。DFS通常使用递归函数或显式的栈数据结构来实现。
在二叉树中的应用场景
前序遍历DFS通常用于前序遍历二叉树即先访问根节点然后递归地访问左子树和右子树。前序遍历用于深度优先搜索问题。中序遍历DFS也可以用于中序遍历二叉树即先递归地访问左子树然后访问根节点最后递归地访问右子树。中序遍历在二叉搜索树中用于获取有序元素。后序遍历DFS还可用于后序遍历二叉树即先递归地访问左子树和右子树最后访问根节点。后序遍历在某些问题中很有用例如计算表达式的值或查找树的高度。
总的来说BFS适用于需要层级遍历或查找最短路径的问题而DFS适用于需要深度优先搜索或对树的结构进行更复杂操作的问题。在二叉树中您可以根据具体问题的要求选择使用BFS或DFS。有时问题可能需要同时使用这两种方法以解决不同的子问题。
