199. Binary Tree Right Side View - Medium
发布时间:2020-12-14 05:17:36 所属栏目:大数据 来源:网络整理
导读: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,4]Output:?[1,4]Explanation: 1 --- / 2 3 --- 5 4 --- ? M1: BFS le
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,4] Output:?[1,4] Explanation: 1 <--- / 2 3 <--- 5 4 <--- ? M1: BFS level order traverse,,每次遍历完一层后,只把这一层最右的数字加入res中 time: O(n),space: O(N) -- N: most number of nodes in one level /** * 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> res = new ArrayList<>(); if(root == null) { return res; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()) { List<Integer> tmp = new ArrayList<>(); int size = q.size(); for(int i = 0; i < size; i++) { TreeNode t = q.poll(); tmp.add(t.val); if(t.left != null) { q.offer(t.left); } if(t.right != null) { q.offer(t.right); } } res.add(tmp.get(tmp.size() - 1)); } return res; } } ? M2: DFS ref:?https://leetcode.com/problems/binary-tree-right-side-view/discuss/56012/My-simple-accepted-solution(JAVA) time: O(n),space: O(n) /** * 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> res = new ArrayList<>(); if(root == null) { return res; } dfs(root,0,res); return res; } public void dfs(TreeNode node,int curLevel,List<Integer> list) { if(node == null) { return; } if(curLevel == list.size()) { list.add(node.val); } dfs(node.right,curLevel + 1,list); dfs(node.left,list); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |