Yuan
0%

199. Binary Tree Right Side View

Posted on Edited on

https://leetcode.com/problems/binary-tree-right-side-view/

Solution1: recursive DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def __init__(self):
        self.k=-1
    def rightSideView(self, R: Optional[TreeNode]) -> List[int]:
        def f(C,k):
            if not C:
                return
            if k>self.k:
                self.k+=1
                ans.append(C.val)
            f(C.right,k+1)
            f(C.left,k+1)
        ans=[]
        f(R,0)
        return ans

Solution2: BFS(one queue + traverse current level by storing length)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rightSideView(self, R: Optional[TreeNode]) -> List[int]:
        if not R:
            return []
        Q=deque([R])
        ans=[]
        while Q:
            L=len(Q)
            for i in range(L):
                C=Q.popleft()
                if i==L-1: # it is the right most node in current level
                    ans.append(C.val)
                if C.left:
                    Q.append(C.left)
                if C.right:
                    Q.append(C.right)
                
        return ans

Solution3: BFS(one queue + None sentinel)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rightSideView(self, R: Optional[TreeNode]) -> List[int]:
        if not R:
            return []
        Q=deque([R,None])
        ans=[]
        while Q:
            C=Q.popleft()
            while C is not None:
                if C.left is not None:
                    Q.append(C.left)
                if C.right is not None:
                    Q.append(C.right)
                prev=C
                C=Q.popleft()
            ans.append(prev.val)
            if len(Q)>0:
                Q.append(None)
        return ans

Solution4: BFS(double queue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def rightSideView(self, R: Optional[TreeNode]) -> List[int]:
        if R is None:
            return []
        Q=deque([R])
        ans=[]
        while Q:
            N=deque()
            ans.append(Q[-1].val)
            while Q:
                C=Q.popleft()
                if C.left:
                    N.append(C.left)
                if C.right:
                    N.append(C.right)
            Q=N
        return ans
    
# or
class Solution:
    def rightSideView(self, R: Optional[TreeNode]) -> List[int]:
        if R is None:
            return []
        Q=deque([R])
        ans=[]
        while Q:
            N=deque()
            while Q:
                C=Q.popleft()
                if C.left:
                    N.append(C.left)
                if C.right:
                    N.append(C.right)
            #last poped node is the right most node
            ans.append(C.val)
            Q=N
        return ans