Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/199.html
199 Binary Tree Right Side View
Given 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:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
@tag-tree
Algorithm
Just save the rightmost node of each level.
Code
Java
-
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Binary_Tree_Right_Side_View { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int currentLevelCount = 1; int nextLevelCount = 0; while (!q.isEmpty()) { TreeNode current = q.poll(); currentLevelCount--; if (current.left != null) { q.offer(current.left); nextLevelCount++; } if (current.right != null) { q.offer(current.right); nextLevelCount++; } if (currentLevelCount == 0) { result.add(current.val); currentLevelCount = nextLevelCount; nextLevelCount = 0; } } return result; } } }
-
// OJ: https://leetcode.com/problems/binary-tree-right-side-view/ // Time: O(N) // Space: O(H) class Solution { vector<int> ans; void dfs(TreeNode *root, int lv) { if (!root) return; if (lv == ans.size()) ans.push_back(root->val); else ans[lv] = root->val; dfs(root->left, lv + 1); dfs(root->right, lv + 1); } public: vector<int> rightSideView(TreeNode* root) { dfs(root, 0); return ans; } };
-
# 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]: ans = [] if root is None: return ans q = deque([root]) while q: ans.append(q[-1].val) for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return ans ############ # 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]: ans = [] if root is None: return ans q = deque([root]) while q: ans.append(q[-1].val) for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return ans ############# # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution(object): def rightSideView(self, root): """ :type root: TreeNode :rtype: List[int] """ def dfs(root, h): if root: if h == len(ans): ans.append(root.val) dfs(root.right, h + 1) dfs(root.left, h + 1) ans = [] dfs(root, 0) return ans