---
# System prepended metadata

title: code tpl
tags: [mock interview, 面試]

---

# 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
 
 
 
```python=
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...]

```python=
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` `面試`