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 是树的最大宽度。在最坏的情况下,树可能是完全二叉树,此时队列中存储的节点数量最多,即树的最大宽度。