Given the root of a binary tree, return the rightmost node at each level of the tree. The output should be a list containing only the values of those nodes.
Example 1
Input:
[1, 3, 4, null, 2, 7, null, 8]
Output: [1, 4, 7, 8]
Example 2
Input:
[1,2,5,3,null,null,null,null,4]
Output: [1, 5, 3, 4]
Explanation
Since the question is asking for the rightmost node at each level, we should recognize that a level-order breadth-first traversal of the binary tree is the most straightforward way to solve this problem.
We can start by initialize an empty list to store the rightmost nodes. Recall that in a level-order traversal, we first find the number of nodes at the current level, and then we use a for-loop to loop over all the nodes at that level. When the count of the for loop is equal to the number of nodes at the current level minus one, we know that the current node is the rightmost node at that level, so we can add it to our list.
class Solution: def rightmostNode(self, root: TreeNode) -> List[int]: if not root: return [] nodes = [] queue = deque([root]) while queue: level_size = len(queue) for i in range(level_size): node = queue.popleft() # current node is the rightmost node if i == level_size - 1: nodes.append(node.val) # add nodes as normal to the queue if node.left: queue.append(node.left) if node.right: queue.append(node.right) return nodes
class Solution { public List<Integer> rightmostNode(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> nodes = new ArrayList<>(); 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(); // current node is the rightmost node if (i == levelSize - 1) { nodes.add(node.val); } // add nodes as normal to the queue if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } return nodes; }}
func rightmostNode(root *TreeNode) []int { if root == nil { return []int{} } var nodes []int queue := []*TreeNode{root} for len(queue) > 0 { levelSize := len(queue) for i := 0; i < levelSize; i++ { node := queue[0] queue = queue[1:] // current node is the rightmost node if i == levelSize-1 { nodes = append(nodes, node.Val) } // add nodes as normal to the queue if node.Left != nil { queue = append(queue, node.Left) } if node.Right != nil { queue = append(queue, node.Right) } } } return nodes}
class Solution { rightmostNode(root: TreeNode | null): number[] { if (!root) { return []; } const nodes: number[] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; // current node is the rightmost node if (i === levelSize - 1) { nodes.push(node.val); } // add nodes as normal to the queue if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } } return nodes; }}
