Breadth-First Search
Rightmost Node
DESCRIPTION (inspired by Leetcode.com)
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]
// class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode() {}
// TreeNode(int val) { this.val = val; }
// TreeNode(int val, TreeNode left, TreeNode right) {
// this.val = val;
// this.left = left;
// this.right = right;Run your code to see results here
Have suggestions or found something wrong?
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 {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 nodeif (i == levelSize - 1) {nodes.add(node.val);}// add nodes as normal to the queueif (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return nodes;}}
What is the time complexity of this solution?
O(m * n * 4^L)
O(n)
O(log n)
O(n log n)