Leetcode 二叉树的右视图

好的，我来用中文详细解释这段代码的算法思想。

问题描述

题目要求给定一个二叉树的根节点，从树的右侧看过去，按从上到下的顺序返回看到的节点值。即，我们需要找到每一层的最右侧节点并将其加入结果中。

算法思想

这道题可以通过广度优先搜索（BFS）来解决。BFS的特点是逐层遍历树的节点，非常适合在每一层获取最右侧的节点。以下是具体的算法步骤：

1. 使用队列进行层序遍历：

   • 我们采用BFS来逐层遍历树，BFS通常会使用队列（Queue）来实现。
   • 首先，将树的根节点放入队列中。

2. 每层节点的遍历：

   • 在每一层开始时，我们记录队列的大小，即当前层的节点数。
   • 然后，我们依次从队列中取出该层的每一个节点，处理这些节点，并将它们的左右子节点加入队列，以便下一层继续遍历。
   • 在遍历当前层的节点时，我们将当前层的最后一个节点（即最右侧的节点）保存下来。

3. 记录每层最右侧的节点：

   • 对于每一层的节点，最后一个处理的节点就是该层的最右侧节点。
   • 因此，在遍历每层的过程中，我们将每层最后一个节点的值添加到结果列表中。

4. 返回结果：

   • 当遍历完所有层后，结果列表中就存储了从上到下每一层的最右侧节点值。
     java solution

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 size = queue.size(); //获取当前层的节点数
            TreeNode rightmostNode = null; //保存当前层的最右侧节点
            for(int i = 0; i < size; ++i) {
                TreeNode currentNode = queue.poll(); //取出当前节点
                rightmostNode = currentNode;
                if(currentNode.left != null) queue.offer(currentNode.left);
                if(currentNode.right != null) queue.offer(currentNode.right);
            }
            if(rightmostNode != null) result.add(rightmostNode.val);
        }
        return result;
    }
}

关键步骤解释

1. 初始化结果列表：List<Integer> result = new ArrayList<>();

   • 用于存储每层的最右侧节点值。

2. 判断根节点是否为空：if (root == null) return result;

   • 如果根节点为空，则直接返回空列表，因为没有节点可以被观察到。

3. 使用队列来实现BFS：

   • Queue<TreeNode> queue = new LinkedList<>(); 初始化一个队列。
   • queue.offer(root); 将根节点加入队列，准备开始逐层遍历。

4. 逐层遍历：

   • while (!queue.isEmpty()) 表示只要队列中还有节点，继续进行遍历。
   • int size = queue.size(); 获取当前层的节点数量。
   • TreeNode rightmostNode = null; 初始化一个变量来保存当前层的最右侧节点。

5. 遍历当前层的所有节点：

   • for (int i = 0; i < size; i++) 遍历当前层的所有节点。
   • TreeNode currentNode = queue.poll(); 从队列中取出当前节点。
   • rightmostNode = currentNode; 每次循环都会更新最右侧节点的值，最后一次更新的节点就是该层的最右侧节点。
   • if (currentNode.left != null) queue.offer(currentNode.left); 将左子节点加入队列（如果存在）。
   • if (currentNode.right != null) queue.offer(currentNode.right); 将右子节点加入队列（如果存在）。

6. 记录每层的最右侧节点：

   • if (rightmostNode != null) result.add(rightmostNode.val); 将当前层的最右侧节点值添加到结果列表中。

7. 返回结果：

   • return result; 当遍历完所有层后，返回结果列表。

时间复杂度

此算法的时间复杂度为 (O(n))，其中 (n) 是树中节点的数量。因为每个节点只会被访问一次。

总结

这段代码通过层序遍历来获取每层的最右侧节点，从而实现了从右侧观察二叉树的效果。最终结果列表中按顺序保存了从上到下每一层的最右侧节点值，符合题目要求。