Compute tree right view and target-sum subarrays

You are given two separate programming tasks.

---

Task 1: Right-side view of a binary tree

You are given the root of a binary tree. Imagine standing on the right side of the tree and looking at it. You can see exactly one node at each depth level: the rightmost node at that level.

Write a function that returns a list (or array) of the values of the nodes that would be visible from the right side, ordered from top to bottom.

Example

Consider this binary tree:

       10
      /  \
     5    20
    / \     \
   3   7     30

From the right side, you see nodes with values: [10, 20, 30].

Input/Output

• Input: root node of a binary tree where each node has:
  • val: integer
  • left: left child pointer (or null)
  • right: right child pointer (or null)
• Output: An array (or list) of integers representing the visible node values from top to bottom.

Constraints

• Number of nodes n can be up to about 10^4.
• Node values can be any 32-bit signed integers.
• The tree does not have to be balanced.

---

Task 2: Count subarrays with a given sum

You are given an integer array nums and an integer k.

Return the total number of contiguous subarrays whose elements sum exactly to k.

Example

• Input: nums = [1, 2, 3], k = 3 Valid subarrays are:
  • [1, 2] (sum = 3)
  • [3] (sum = 3) So the answer is 2.

Input/Output

• Input:
  • An integer array nums of length n.
  • An integer k.
• Output: A single integer representing the number of contiguous subarrays whose sum equals k.

Constraints

• 1 <= n <= 10^5 (you should aim for an algorithm that is close to O(n)).
• Elements of nums can be negative, zero, or positive (32-bit signed integers).
• k is a 32-bit signed integer.

You may implement both functions in any language of your choice.

Part 1: Right-Side View of a Binary Tree

You are given a binary tree encoded as a level-order list. Each element is either an integer node value or None for a missing child.

Return the values of the nodes visible when looking at the tree from the right side. At each depth, only the rightmost existing node should be included.

For example, the level-order list [10, 5, 20, 3, 7, None, 30] represents a tree whose right-side view is [10, 20, 30].

Constraints

• 0 <= number of list entries <= 10^4
• Node values are 32-bit signed integers
• The input list is a valid level-order encoding of a binary tree
• The tree may be empty and does not need to be balanced

Examples

Example 1

Input: [10, 5, 20, 3, 7, None, 30]
Output: [10, 20, 30]

Explanation: The rightmost node at each depth is 10, then 20, then 30.

Example 2

Input: [1, 2, 3, None, 5, None, 4]
Output: [1, 3, 4]

Explanation: At level 2, node 3 hides node 2 from the right. At level 3, node 4 is the rightmost visible node.

Hints

1. A breadth-first traversal lets you process the tree level by level; the last node you visit in each level is the visible one.
2. An alternative is depth-first search that visits right children before left children and records the first node seen at each depth.

Part 2: Count Subarrays With a Given Sum

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum is exactly k.

A subarray must contain consecutive elements. Because the array can include negative numbers, zero, and positive numbers, you should aim for an algorithm close to O(n).

Constraints

• 0 <= n <= 10^5
• Each element of nums is a 32-bit signed integer
• k is a 32-bit signed integer
• An O(n) or near-O(n) solution is expected

Examples

Example 1

Input: ([1, 2, 3], 3)
Output: 2

Explanation: The valid subarrays are [1, 2] and [3].

Example 2

Input: ([1, 1, 1], 2)
Output: 2

Explanation: The subarrays [1, 1] at indices (0,1) and (1,2) both sum to 2.

Hints

1. Track a running prefix sum as you scan the array.
2. If current_sum - k has appeared before, then each previous occurrence marks a subarray ending at the current index with sum k.