网站开发的技术难点,网站建设 搜狐号,sem优化公司,个人小程序开发多少钱今日题目#xff1a; 144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历102. 二叉树的层序遍历107. 二叉树的层序遍历 II199. 二叉树的右视图637. 二叉树的层平均值429. N 叉树的层序遍历515. 在每个树行中找最大值116. 填充每个节点的下一个右侧节点指针117. … 今日题目 144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历102. 二叉树的层序遍历107. 二叉树的层序遍历 II199. 二叉树的右视图637. 二叉树的层平均值429. N 叉树的层序遍历515. 在每个树行中找最大值116. 填充每个节点的下一个右侧节点指针117. 填充每个节点的下一个右侧节点指针 II104. 二叉树的最大深度111. 二叉树的最小深度 目录 Problem 1二叉树的递归遍历 【easy】Problem 2二叉树的迭代遍历 【classic】2.1 前序遍历 迭代版2.2 中序遍历 迭代版2.3 后序遍历 迭代版 【必背】 Problem 3二叉树的层次遍历 【classic】LC 102. 二叉树的层序遍历其他例题 今天主要学习了二叉树的递归遍历、迭代遍历和层序遍历其中递归遍历和层序遍历都很简单而迭代遍历的代码写起来稍有困难这部分需要在理解的基础上把伪代码背过。
Problem 1二叉树的递归遍历 【easy】
递归遍历二叉树很简单了可以拿这三个遍历题练练手 144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历 Problem 2二叉树的迭代遍历 【classic】 △ 第一次访问 ○ 第二次访问☆ 第三次访问 2.1 前序遍历 迭代版 144. 二叉树的前序遍历 伪代码思路
void preOrder2(TreeNode T) {Stack S;TreeNode p T;while (p !null !S.empty()) {if (p) {visit(p); // 第一次经过时访问之S.push(p); p p.left(); // 一路向左} else {S.pop(p);p p.right(); // 向右走step 10}}
}Java 代码实现
class Solution {public ListInteger preorderTraversal(TreeNode root) {if (root null) {return Collections.emptyList();}ListTreeNode stack new ArrayList();ListInteger result new ArrayList();TreeNode p root;while (p ! null || !stack.isEmpty()) {if (p ! null) {result.add(p.val);stack.addLast(p);p p.left;} else {p stack.removeLast();p p.right;}}return result;}
}2.2 中序遍历 迭代版 94. 二叉树的中序遍历 伪代码如下
void inOrder2(TreeNode T) {Stack S;TreeNode p T; // p 是遍历指针while (p ! null || !S.empty()) { // 栈不空或者 p 不空时循环// 一路向左直到空节点if (p) {S.push(p); // 当前节点入栈p p.left; // 向左走}// 遇到空节点else {S.pop(p); // 访问栈顶元素step9由于接下来要访问之故 popvisit(p); // 访问之p p.right; // 向右子树走step10}}
}2.3 后序遍历 迭代版 【必背】 145. 二叉树的后序遍历 这个建议直接背过掌握这个算法思路后并不难背大不了多写几遍代码。
算法思路① 一路向左走并入栈直到空节点② 碰到空节点后读取栈顶元素但不弹出step9如果存在右孩子并且未访问过为了确定之前是从左孩子返回过来的则向右走否则栈顶元素出栈并访问之。
为了区分返回到一个节点时是从左子树回来的还是从右子树回来的代码设定了辅助指针 recent它指向最近访问过的节点当 p.right ! recent 时表示这是从左子树回来的还没有访问过右子树。
后序遍历迭代版特点
当一个节点的左右子树都被访问后才能出栈pop。实际上当访问一个节点 p 时栈中节点恰好是 p 节点的所有祖先从栈底到栈顶再加上 p 节点刚好构成从根节点到 p 节点的一条路径。很多算法设计都利用了这一思想比如求根到某节点的路径求两个节点的最近公共祖先等。
伪代码如下
void postOrder2(TreeNode T) {Stack S;TreeNode p T, recent null;while (p ! null !S.empty()) {if (p) {S.push(p);p p.left;} else { // 向右p S.top(); // 读取栈顶节点if (p.right p.right ! recent) { // 若存在右孩子且未被访问过p p.right; // 向右走} else { // 否则弹出节点并访问之S.pop(p);visit(p);recent p; // 更新最近访问的节点p null; // 节点访问完后重置 p 指针}} // end else} // end while
}代码实现
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListTreeNode stack new ArrayList();ListInteger result new ArrayList();TreeNode p root, recent null;while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.addLast(p);p p.left;} else {p stack.getLast();if (p.right ! null recent ! p.right) {p p.right;} else {result.add(p.val);recent p;stack.removeLast();p null;}}}return result;}
}Problem 3二叉树的层次遍历 【classic】
层序遍历的模板可以解决一大类问题需要谨记。 算法思想
初始化一个辅助队列 Q根节点入队若 Q 非空则队头节点出队并访问之并将其左右孩子入队如果有的话重复 3 直至队空。
伪代码实现
void levelOrder(TreeNode T) {Queue Q; // 1. 初始化一个辅助队列TreeNode p;Q.offer(T); // 2. 根节点入队while (!Q.empty()) { // 3. 若 Q 非空则int sz Q.size(); // 这一层的节点个数// 依次将这一层的节点出队for (int i 0; i sz; i) {var curr Q.poll();visit(curr); // 访问之// 将左右子节点加入队列if (curr.left ! null) {Q.offer(curr.left);}if (curr.right ! null) {Q.offer(curr.right);}}} // 4. 重复直至队空return;
}LC 102. 二叉树的层序遍历 102. 二叉树的层序遍历 这是经典使用层序遍历来获取二叉树的层序遍历顺序基本与模板一致
class Solution {public ListListInteger levelOrder(TreeNode root) {if (root null) {return Collections.emptyList();}DequeTreeNode queue new LinkedList(); // 队列queue.addLast(root);ListListInteger result new ArrayList();while (!queue.isEmpty()) {int sz queue.size();ListInteger levelNums new ArrayList();for (int i 0; i sz; i) {var node queue.removeFirst();levelNums.add(node.val);// 将左右子节点加入队列if (node.left ! null) {queue.addLast(node.left);}if (node.right ! null) {queue.addLast(node.right);}}result.add(levelNums);}return result;}
}其他例题
借助二叉树的层序遍历的模板可以一口气解决下面十个题目 102. 二叉树的层序遍历107. 二叉树的层序遍历 II199. 二叉树的右视图637. 二叉树的层平均值429. N 叉树的层序遍历515. 在每个树行中找最大值116. 填充每个节点的下一个右侧节点指针117. 填充每个节点的下一个右侧节点指针 II104. 二叉树的最大深度111. 二叉树的最小深度
