LeetCode-199-二叉树的右视图 LeetCode-199-二叉树的右视图

二叉树的右视图

题目描述：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例说明请见LeetCode官网。
【LeetCode-199-二叉树的右视图】来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：层序遍历二叉树

利用队列先进先出的特点层序遍历二叉树，具体处理过程如下：

初始化一个队列，并将根节点添加到队列中，作为第一层；

循环遍历队列中每一层的元素，并暂存到二维List中，并将下一层的节点按从左到右的顺序加入到队列中；

直到队列为空，遍历结束。

最后，按顺序从二维List中取每一层的最后一个元素，并返回。

import com.kaesar.leetcode.TreeNode; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class LeetCode_199 { /** * 层序遍历 * 通过使用队列先进先出的方式遍历二叉树 * * @param root * @return */ public static List rightSideView(TreeNode root) { if (root == null) { return new ArrayList<>(); } // 暂存每一层的节点 List> numsList = new ArrayList<>(); Queue nodes = new LinkedList<>(); nodes.add(root); // 遍历每一层的节点，并将下一层的节点按从左到右的顺序加入到队列中 while (!nodes.isEmpty()) { List nums = new ArrayList<>(); int count = nodes.size(); for (int i = 0; i < count; i++) { TreeNode cur = nodes.poll(); nums.add(cur.val); if (cur.left != null) { nodes.add(cur.left); } if (cur.right != null) { nodes.add(cur.right); } } numsList.add(nums); }List result = new ArrayList<>(); // 按顺序取每一层的最后一个元素 for (List integers : numsList) { result.add(integers.get(integers.size() - 1)); } return result; }public static void main(String[] args) { /** * 测试用例： *1 *23 *54 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.right = new TreeNode(5); root.right.right = new TreeNode(4); // 期望输出： 1,3,4 for (Integer integer : rightSideView(root)) { System.out.print(integer + " "); } } }