# 199. Binary Tree Right Side View

1
/ \
2 3
/ \
4 5
/
6
1
/ \
2 3
/\ / \
4 5 6 7

N/2
[1 , 3, 5, 6]

1. BFS trasver all node
2. 1->l0, 2, 3->l1
3. [1, 2->3, 4->5, 6 ]
4.idx 0 1 2 3

def sol(root):
    
    if not root:
        return []
    
    q = deque([(root, 0)]) # node, idx
    ans = []
    while q:
        # q = 1 2 3 4 5 6 
        node, idx = q.popleft()
        #2 , 1
        #3, 1
        # 4, 2
        # 5, 2
        #6, 3
        if len(ans) == idx:
            ans.append(-1)
            
        ans[idx] = node.val
        # ans = [1, 2->3, 4->5, 6]
        
        if node.left:
            q.append((node.left, idx+1))
        if node.right:
            q.append((node.right, idx+1))
    
    # 1, 3, 5, 6
    # N: number of nodes
    # TC : O(N)
    # SC: O(N) -> O( N/2) -> O(N)
    return ans
        

1
/ \
2 3
/ \
4 5
/ /
6 7

6 4 2 5 1 3 -> in order

-> ans = [6 4 2 5 1 3]

1. recursive
retrun fn(left) + root.val + fn(right)
2. stack
1. push all left until none

2. pick last one, if last one has right -> repeat 1

stack [1, 2, 4, 6]
stack [1, 2, 4]
stack [1, 2]
stack [1, 5, 7]
stack [1,]

ans [6, 4, 2, 7, 5...]

ans = []
def sol(root):
    if not root:
        return []
    sol(root.left)
    ans.append(root.val)
    sol(root.right)
    
# TC: O(N)
# SC: 


def sol(root):
    if not root:
        return []
    
    stack = []
    # []
    def add(node):
        stack.append(node)
        while stack[-1].left:
            stack.append(stack[-1].left)
            
            
    add(root)
    ans = []
    while stack:
        cur = stack.pop()
        # 4 2 5 1
        if cur.right:
            add(cur.right)
        ans.append(cur.val)
        #ans = [4, 2, 5, 1, 3]
    return ans
    #ans = [4, 2, 5, 1, 3]
    
    # N: number of nodes
    # TC: O(N)
    # SC: O(N)
    #   1
    

1
/
2
/
4
/
5

1
/ \
2 3
/ \
4 5
###### tags: `mock interview` `面試`