binary_tree_right_side_view
1from itertools import chain 2from collections import deque 3from typing import Optional 4from utils import TreeNode 5 6 7# @leet start 8class Solution: 9 def rightSideView(self, root: Optional[TreeNode]) -> list[int]: 10 """ 11 This problem asks us to show the right side view of a binary tree. 12 If we were on the right side of the binary tree, which nodes would we see? 13 Imagine a level-order traversal of the tree. We'd always want the rightmost 14 node. So, we do a traversal level by level, and left to right, and then place 15 the last node we've seen on each level into a list and return the list. 16 17 This works because we always save the last node which we've seen, and since 18 we're going from left to right, that will always be the rightmost node. 19 """ 20 if not root: 21 return [] 22 23 res = [] 24 q = deque() 25 q.append((root, 0)) 26 27 while q: 28 node, level = q.popleft() 29 if len(res) <= level: 30 res.append([node.val]) 31 else: 32 res[level][-1] = node.val 33 34 if node.left: 35 q.append((node.left, level + 1)) 36 if node.right: 37 q.append((node.right, level + 1)) 38 39 return list(chain(*res)) 40 41 42# @leet end 43 44 45def test(): 46 assert 2 + 2 == 4
class
Solution:
9class Solution: 10 def rightSideView(self, root: Optional[TreeNode]) -> list[int]: 11 """ 12 This problem asks us to show the right side view of a binary tree. 13 If we were on the right side of the binary tree, which nodes would we see? 14 Imagine a level-order traversal of the tree. We'd always want the rightmost 15 node. So, we do a traversal level by level, and left to right, and then place 16 the last node we've seen on each level into a list and return the list. 17 18 This works because we always save the last node which we've seen, and since 19 we're going from left to right, that will always be the rightmost node. 20 """ 21 if not root: 22 return [] 23 24 res = [] 25 q = deque() 26 q.append((root, 0)) 27 28 while q: 29 node, level = q.popleft() 30 if len(res) <= level: 31 res.append([node.val]) 32 else: 33 res[level][-1] = node.val 34 35 if node.left: 36 q.append((node.left, level + 1)) 37 if node.right: 38 q.append((node.right, level + 1)) 39 40 return list(chain(*res))
10 def rightSideView(self, root: Optional[TreeNode]) -> list[int]: 11 """ 12 This problem asks us to show the right side view of a binary tree. 13 If we were on the right side of the binary tree, which nodes would we see? 14 Imagine a level-order traversal of the tree. We'd always want the rightmost 15 node. So, we do a traversal level by level, and left to right, and then place 16 the last node we've seen on each level into a list and return the list. 17 18 This works because we always save the last node which we've seen, and since 19 we're going from left to right, that will always be the rightmost node. 20 """ 21 if not root: 22 return [] 23 24 res = [] 25 q = deque() 26 q.append((root, 0)) 27 28 while q: 29 node, level = q.popleft() 30 if len(res) <= level: 31 res.append([node.val]) 32 else: 33 res[level][-1] = node.val 34 35 if node.left: 36 q.append((node.left, level + 1)) 37 if node.right: 38 q.append((node.right, level + 1)) 39 40 return list(chain(*res))
This problem asks us to show the right side view of a binary tree. If we were on the right side of the binary tree, which nodes would we see? Imagine a level-order traversal of the tree. We'd always want the rightmost node. So, we do a traversal level by level, and left to right, and then place the last node we've seen on each level into a list and return the list.
This works because we always save the last node which we've seen, and since we're going from left to right, that will always be the rightmost node.
def
test():