199. Binary Tree Right Side View
Medium LeetCodeGiven the root of 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 1
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Example 3
Input: root = [1,null,3]
Output: [1,3]
Example 4
Input: root = []
Output: []
Constraints
- The number of nodes in the tree is in the range [0, 100]
- -100 <= Node.val <= 100
How to solve the problem
Code
- Recursion (DFS)
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
# DFS
ans = []
def dfs(node, depth):
if node is None:
return
if depth == len(ans):
ans.append(node.val)
dfs(node.right, depth+1)
dfs(node.left, depth+1)
dfs(root, 0)
return ans
Complexity
- Time complexity: O(n), n == number of nodes
- Space complexity: O(h), h == height of tree
Comments
No comments yet. Be the first to comment!