leetcode hot100【LeetCode 199. 二叉树的右视图】java实现

LeetCode 199. 二叉树的右视图

题目描述

给定一个二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧可见的节点值。

示例：

输入: [1,2,3,null,null,5,null,6]

    1/ \2   3\   \5   6

输出: [1, 3, 6]

Java 实现代码

/*** 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> result = new ArrayList<>();if (root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();if(i == levelSize -1){result.add(node.val);}if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}}return result;}
}

解题思路

这个问题可以通过层次遍历（BFS）来解决。我们使用一个队列来存储每一层的节点，然后逐层遍历。在每一层，我们添加节点的值到结果列表中，然后添加它们的子节点到队列中。由于我们是按照从顶部到底部的顺序遍历，所以每一层的最后一个节点就是从右侧可见的节点。

复杂度分析

• 时间复杂度：O(N)，其中 N 是树中节点的数量。因为每个节点都会被访问一次。
• 空间复杂度：O(M)，其中 M 是树的最大宽度。在最坏的情况下，树可能是完全二叉树，此时队列中存储的节点数量最多，即树的最大宽度。