题目

给定一个二叉树，按照自上向下的顺序，返回从右侧所能看到的所有节点值。
如下图，返回结果是：1,3,7

分析

• 可使用BFS/DFS遍历二叉树
• 返回右视图的节点值
  #题解
  BFS遍历二叉树，返回每层最右节点值

  public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    // 使用队列实现层序遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      // 保存每层最右节点
      TreeNode rightNode = null;
      // 每个for循环遍历一层节点
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        rightNode = node;
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
      }
      // 将每层最右节点数值保存到结果中
      res.add(rightNode.val);
    }
    return res;
  }

总结

本题的解题思路是遍历树，找到对应规则下的节点并返回。按照此思路同样可以解决“二叉树的左视图”、“多叉树的左/右视图”等，感兴趣的读者可自行练习