199. Right view of binary trees

Title source: leetcode-cn.com/problems/bi…

The title

Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right side, in order from top to bottom.

Example:

Input: [5, 1, 2, 3, null, null, 4] output: [1, 3, 4] explanation: < 1-2 3 < / \ - \ \ 5 4 < -- -- -Copy the code

Their thinking

Idea 1: breadth optimization search

When traversing a binary tree hierarchically, the rightmost node of each layer is the last to be accessed. They want to return the value of the node visible from the right, which is the rightmost node in each of these layers. Keep the access nodes at the end of each layer and get the desired answer.

Queue storage is used here.

Specific can refer to the code to understand.

Idea 2: depth optimization search

Again, this problem can be solved using deeply optimized search.

During the search, we first visit the right subtree, then the left subtree. So the first node in each layer is the rightmost node. At this point, as long as you know the depth of the binary tree, you can get the final answer.

Specific can refer to the code to understand.

Code implementation

Code implementation | breadth search optimization
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def rightSideView(self, root: TreeNode) -> List[int]: if root == None: From collections import deque queue = deque([root]) res = [] while queue: Size = len(queue) # for I in range(size): node = queue.popleft() # if node.left! = None: queue.append(node.left) # add right node to queue if node.right! = None: queue.append(node.right) # queue first in, first out, if I = size-1, # then this is the rightmost node, this is the result of the return list if I == size-1: res.append(node.val) return resCopy the code
Code implementation | depth search optimization
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def rightSideView(self, root: TreeNode) -> List[int]: res = [] def _dfs(node, depth): if node == None: If depth == len(res); if depth == len(res); if depth == len(res); if depth == len(res); Res.append (node.val) # Depth += 1 _dfs(node.right, depth) _dfs(node.left, depth) _dfs(root, 0) return resCopy the code

Achieve results

Optimized results | breadth search

Implement optimized search results | depth

This is the main content of solving the 199. Right View of binary tree problem by using the idea of breadth optimized search or depth optimized search.

Welcome to follow the wechat official account “Collection of Books”