Problem
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
Solution
Comprare the depth. DFS.
Keep track of the current depth. And the length of current answer is the previous depth.
Traverse right to left
If current_depth > previous depth, then it appears in the right view.
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
ans = []
self.print(root, ans, 0)
return ans
def print(self, root, ans, depth):
if not root:
return
if depth + 1 > len(ans): ans.append(root.val)
self.print(root.right, ans, depth+1)
self.print(root.left, ans, depth+1)