【二叉树-BFS系列1】二叉树的右视图、二叉树的锯齿形层次遍历
2024-10-09 13:58:03
题目 199. 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- BFS层序遍历， 将每一层最后一个节点加入答案中。
- 需要区分层次时，可以如下代码在while中加入for当层的循环。
- 树的BFS遍历：
根结点入队；
while队列非空：
弹出队首节点，
处理队首节点，
左孩子节点非空则入队，右孩子节点非空则入队。
待做
此题DFS也可解。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
if(root!=null){
q.offer(root);
}
while(!q.isEmpty()){
int size = q.size();
for(int i=0;i<size;++i){
TreeNode node = q.poll();
if(node.left!=null){
q.offer(node.left);
}
if(node.right!=null){
q.offer(node.right);
}
if(i==size-1){
res.add(node.val);
}
}
}
return res;
}
}
题目 103. 二叉树的锯齿形层次遍历
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
题解
法一:（推荐）
双端队列实现。
注意同一层弹出节点和插入子节点一定是在队列的两端，否则会造成混乱，进而可推出一个节点的左右子节点的具体插入顺序。
奇数层按正常队首出队，左右入队尾。
偶数层则队尾出队，为了保证队中按正常顺序右左孩子入队首。
法二：
用两个栈分别存奇数层和偶数层，很好的利用栈的特性实现之字形遍历。
代码（法一：双端队列）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ansList = new LinkedList<List<Integer>>();
Deque<TreeNode> q = new LinkedList<>();
if(root!=null){
q.addLast(root);
}
boolean rightToLeft=true;
while(!q.isEmpty()){
List<Integer> list = new LinkedList<>();
int size = q.size();//size()会在循环过程中改变
for(int i=0;i<size;++i){//
if(rightToLeft){
TreeNode node = q.pollFirst();//弹出队首
list.add(node.val);
if(node.left!=null){
q.addLast(node.left);//左右节点顺序加入队尾，下次从尾部弹出
}
if(node.right!=null){
q.addLast(node.right);
}
}else{
TreeNode node = q.pollLast();//弹出队尾
list.add(node.val);
if(node.right!=null){//右左节点顺序加入队首，下次从队首弹出
q.addFirst(node.right);
}
if(node.left!=null){
q.addFirst(node.left);
}
}
}
ansList.add(list);
rightToLeft=!rightToLeft;
}
return ansList;
}
}
代码(法二：两个栈实现)
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
int layer=1;
Stack<TreeNode> sOdd=new Stack<>();
Stack<TreeNode> sEven=new Stack<>();
ArrayList<ArrayList<Integer>> ansList=new ArrayList<ArrayList<Integer>>();
if(pRoot==null) {
return ansList;
}
sOdd.push(pRoot);
while(!sOdd.isEmpty()||!sEven.isEmpty()) {
if(layer%2==1) {
ArrayList<Integer> arrList=new ArrayList<>();
while(!sOdd.isEmpty()) {
TreeNode node=sOdd.pop();
if(node!=null) {//
arrList.add(node.val);
sEven.push(node.left);
sEven.push(node.right);
}
}
if(!arrList.isEmpty()) {
ansList.add(arrList);
++layer;
}
}
else {
ArrayList<Integer> arrList=new ArrayList<>();
while(!sEven.isEmpty()) {
TreeNode node=sEven.pop();
if(node!=null) {
arrList.add(node.val);
sOdd.push(node.right);
sOdd.push(node.left);
}
}
if(!arrList.isEmpty()) {
ansList.add(arrList);
++layer;
}
}
}
return ansList;
}
}
最新文章
- JDK中常见的package
- 【英语】Bingo口语笔记(70) - 最易忽略的2个连读技巧
- 如何判断js中的数据类型（转）
- html5实现渐变效果
- java 读取文件到String(解决中文乱码)
- 【转】CPU调度
- MySQL锁等待分析【2】
- CSS优先级、引入方式、Hack
- UML－状态图，顺序图，活动图
- 十三、oracle 数据字典和动态性能视图
- ajax中url赋json格式的值时发生中文乱码的相关问题
- [Luogu2617]Dynamic Ranking
- pytest进阶之conftest.py
- win10 下JDK10的下载安装与环境变量配置
- 聊聊Java的final关键字
- 【Linux】war包的解压与压缩
- 【React】使用 create-react-app 快速构建 React 开发环境
- pycurl mac 安装报错Curl is configured to use SSL,
- ARP/RARP
- Linux Cache 机制探究