当前位置：首页 > news >正文

2025年- H51-Lc159 --199. 二叉树的右视图(层序遍历，队列）--Java版

news 2025/5/31 17:38:13

1.题目描述

在这里插入图片描述

2.思路

方法一：
返回一个从右侧看二叉树时能看到的所有节点的值。右视图中的每一层只能看到最右边的节点。可以使用层序遍历（BFS），每次遍历一层时，记录该层的最后一个节点的值。
方法二补充：
在这里插入图片描述

3.代码实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;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;}}
public class H199 {public List<Integer> rightSideView(TreeNode root) {//1，创建一个结果List，每次遍历一层时，记录该层的最后一个节点的值。List<Integer> result=new ArrayList<>();if(root==null) return result;Queue<TreeNode> dq=new LinkedList<>();//2. 把根节点加入队列dq.offer(root);//3.当队列不为空while(!dq.isEmpty()) {//4.记录当前队列的长度（也就是每一层的个数）int size=dq.size();for(int i=0;i<size;i++){TreeNode nowNode=dq.poll();//5.删除并返回头部元素//6. 如果是该层的最后一个节点，加到结果里if(i==size-1){result.add(nowNode.val);//把当前节点的值加入}if(nowNode.left!=null){dq.offer(nowNode.left);//7.把当前节点的左孩子加入}if(nowNode.right!=null){dq.offer(nowNode.right);//8.把当前节点的右孩子加入}}}return result;}public static void main(String[] args){H199 test=new H199();TreeNode node5=new TreeNode(5);TreeNode node4=new TreeNode(4);TreeNode node3=new TreeNode(3);TreeNode node2=new TreeNode(2,node4,node5);TreeNode root=new TreeNode(1,node2,node3);List<Integer> res=test.rightSideView(root);System.out.print(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;*     }* }*/
class Solution {public List<Integer> rightSideView(TreeNode root) {ArrayList<Integer> ans = new ArrayList<>();if(root == null){return ans;}Queue<TreeNode> que = new LinkedList<>();que.add(root);while (!que.isEmpty()){int len = que.size();TreeNode node = new TreeNode(101);for (int i = 0; i < len; i++) {node = que.poll();if(node.left != null){que.add(node.left);}if(node.right != null){que.add(node.right);}}ans.add(node.val);}return ans;}
}