199. Binary Tree Right Side View
Source
https://leetcode.com/problems/binary-tree-right-side-view/
Intuition
At each level we want the rightmost node
Traverse the tree by level
Add elements left to right
Discard elements in order they are added
Last element at the level is part of the answer
Level order - BFS
---
Recursive
In order is reverse, first right child, then left
Use a nice trick .. ans.size() == level to add element on first dfs call at that level
---
Time - O(n)
Space - O(n)
https://leetcode.com/problems/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 <------
Intuition
At each level we want the rightmost node
Traverse the tree by level
Add elements left to right
Discard elements in order they are added
Last element at the level is part of the answer
Level order - BFS
---
Recursive
In order is reverse, first right child, then left
Use a nice trick .. ans.size() == level to add element on first dfs call at that level
---
Time - O(n)
Space - O(n)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * 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> ans = new ArrayList<Integer>(); | |
| if (root == null) { | |
| return ans; | |
| } | |
| dfs(root, ans, 0); | |
| return ans; | |
| } | |
| private void dfs(TreeNode node, List<Integer> ans, int depth) { | |
| if (node == null) { | |
| return; | |
| } | |
| if (depth == ans.size()) { | |
| ans.add(node.val); | |
| } | |
| // Root, Right, Left to save rightmost element of next level first | |
| dfs(node.right, ans, depth + 1); | |
| dfs(node.left, ans, depth + 1); | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for a binary tree node. | |
| * public class TreeNode { | |
| * int val; | |
| * TreeNode left; | |
| * TreeNode right; | |
| * TreeNode() {} | |
| * TreeNode(int val) { this.val = val; } | |
| * TreeNode(int val, TreeNode left, TreeNode right) { | |
| * this.val = val; | |
| * this.left = left; | |
| * this.right = right; | |
| * } | |
| * } | |
| */ | |
| class Solution { | |
| public List<Integer> rightSideView(TreeNode root) { | |
| List<Integer> ans = new ArrayList<Integer>(); | |
| if (root == null) { | |
| return ans; | |
| } | |
| Queue<TreeNode> q = new LinkedList<TreeNode>(); | |
| q.offer(root); | |
| boolean last = true; | |
| while (!q.isEmpty()) { | |
| int size = q.size(); | |
| last = true; | |
| for (int i = 0; i < size; i++) { | |
| TreeNode node = q.poll(); | |
| if (last) { | |
| last = false; | |
| ans.add(node.val); | |
| } | |
| if (node.right != null) { | |
| q.offer(node.right); | |
| } | |
| if (node.left != null) { | |
| q.offer(node.left); | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
