Rightmost Node
DESCRIPTION (credit 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.
EXAMPLES
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,4]
Output: [1, 5, 3, 4]
Run your code to see results here
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 nodeif i == level_size - 1:nodes.append(node.val)# add nodes as normal to the queueif node.left:queue.append(node.left)if node.right:queue.append(node.right)return nodes
Complexity Analysis
Time Complexity: O(N) where N is the number of nodes in the tree. We visit each node exactly once, and each node, we perform a constant amount of work, so the time complexity is O(N).
Space Complexity: O(N). In the worst case, each node in the tree is on its own level, so the output list will contain N elements.
© 2024 Optick Labs Inc. All rights reserved.
Loading comments...