[Leetcode] 199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150

initial

This reminded me of the prioritising the moves in the pipe dfs problem, where up,horizontal,down is of the priority order.

Basically this q wants to input the node in first come first serve way with the rightmost node being the highest priority and the leftmost node being the lowest priority.

solution

solved

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans= []
        def traverse(node,depth):
            if not node:
                return
            if len(ans)+1==depth:
                ans.append(node.val)
            if node.right:
                traverse(node.right,depth+1)
            if node.left:
                traverse(node.left,depth+1)
        traverse(root,1)
        return ans

initial

o(n) time cuz each node traversed once
o(h) space where if it is balanced, it is log n, and if skewed it is n.